考虑统计每个数字的贡献。设f[i]为前缀i中该数的出现次数，则要统计f[r]-f[l]>(r-l)/2的数对个数，也即2f[r]-r>2f[l]-l。
注意到所有数的f的总变化次数是线性的，考虑对每次变化进行统计。
对于当前考虑位置i，统计r∈[i,nxt[a[i]])时a[i]的贡献。如果将之前的所有2f[l]-l扔进一个线段树里，可以发现要统计的是终点在一段区间内的前缀和的和。那么不属于该区间的每个2f[l]-l都会被统计nxt[a[i]]-i次，属于该区间的2f[l]-l的被统计次数构成一个等差数列，维护区间和的同时再维护区间前缀和的和即可。统计完后把这段作为l的贡献加进去，就是一个线段树区间加。
写的是动态开点，然而在下传标记的时候忘记开新点了，于是浪费了两个小时宝贵的人生。bzoj上T掉了然而没心情卡常了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 500010 int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int n,a[N],nxt[N],p[N],f[N],cnt,root[N]; ll ans=0; struct data{int l,r,sum,lazy;ll pre; }tree[N*35]; void update(int &k,int l,int r,int x) { if (!k) k=++cnt; tree[k].sum+=(r-l+1)*x; tree[k].pre+=1ll*x*(r-l+1)*(r-l+2)>>1; tree[k].lazy+=x; } void down(int k,int l,int r) { update(tree[k].l,l,l+r>>1,tree[k].lazy),update(tree[k].r,(l+r>>1)+1,r,tree[k].lazy); tree[k].lazy=0; } int querys(int k,int l,int r,int x,int y) { if (!k) return 0; if (l==x&&r==y) return tree[k].sum; if (tree[k].lazy) down(k,l,r); int mid=l+r>>1; if (y<=mid) return querys(tree[k].l,l,mid,x,y); else if (x>mid) return querys(tree[k].r,mid+1,r,x,y); else return querys(tree[k].l,l,mid,x,mid)+querys(tree[k].r,mid+1,r,mid+1,y); } ll querypre(int k,int l,int r,int x,int y) { if (!k) return 0; if (l==x&&r==y) return tree[k].pre; if (tree[k].lazy) down(k,l,r); int mid=l+r>>1; if (y<=mid) return querypre(tree[k].l,l,mid,x,y); else if (x>mid) return querypre(tree[k].r,mid+1,r,x,y); else return querypre(tree[k].l,l,mid,x,mid)+querypre(tree[k].r,mid+1,r,mid+1,y)+1ll*querys(tree[k].l,l,mid,x,mid)*(y-mid); } void ins(int &k,int l,int r,int x,int y) { //cout<<l-n<<' '<<r-n<<' '<<x-n<<' '<<y-n<<endl; if (!k) k=++cnt; if (l==x&&r==y) {update(k,l,r,1);return;} if (tree[k].lazy) down(k,l,r); int mid=l+r>>1; if (y<=mid) ins(tree[k].l,l,mid,x,y); else if (x>mid) ins(tree[k].r,mid+1,r,x,y); else ins(tree[k].l,l,mid,x,mid),ins(tree[k].r,mid+1,r,mid+1,y); tree[k].sum=tree[tree[k].l].sum+tree[tree[k].r].sum; tree[k].pre=tree[tree[k].l].pre+tree[tree[k].r].pre+1ll*tree[tree[k].l].sum*(r-mid); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj5110.in","r",stdin); freopen("bzoj5110.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read();read(); for (int i=1;i<=n;i++) { a[i]=read()+1; if (!p[a[i]]) ins(root[a[i]],0,n*2,n+1-i,n); nxt[p[a[i]]]=i,p[a[i]]=i; } for (int i=1;i<=n;i++) if (!nxt[i]) nxt[i]=n+1; for (int i=1;i<=n;i++) { f[a[i]]++; int x=2*f[a[i]]-(nxt[i]-1),y=2*f[a[i]]-i; ans+=1ll*querys(root[a[i]],0,n*2,0,n+x-2)*(y-x+1); ans+=querypre(root[a[i]],0,n*2,n+x-1,n+y-1); ins(root[a[i]],0,n*2,x+n,y+n); } cout<<ans; return 0; }