我们考虑一对(j,i)的贡献,假如\(s[i] \neq s[j]\),就会产生贡献,它们的贡献就是
min(j,n-i-+1),那么我们考虑分开计算两种即可
j-1<=n-i
j-1>=n-i
然后减去对称的贡献。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m;
ll a[N],s,j,c[N],i;
ll ans;
int main() {
// #ifdef LOCAL
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// #endif
scanf("%d",&n);
fo(i,1,n) scanf("%lld",&a[i]);
if (n&1) {
s=n/2+2;
c[a[n/2+1]]++;
}
else s=n/2+1;
fo(i,s,n) {
j=n-i+1;
c[a[j]]++;
ans+=(i-j-c[a[i]])*(n-i+1);
// printf("%d ",(i-j-c[a[i]])*(n-i+1));
c[a[i]]++;
}
memset(c,0,sizeof(c));
s=n/2;
if (n&1) c[a[n/2+1]]++;
fd(j,s,1) {
i=n-j+1;
c[a[i]]++;
ans+=(i-j-c[a[j]])*j;
c[a[j]]++;
}
fo(i,1,n/2) {
if (a[i]^a[n-i+1]) {
ans-=i;
}
}
printf("%lld",ans);
return 0;
}