Description
Yazid有一个长度为n的序列A，下标从1至n。显然地，这个序列共有n(n+1)/2个子区间。对于任意一个子区间[l,r]
，如果该子区间内的众数在该子区间的出现次数严格大于(r-l+1)/2（即该子区间长度的一半），那么Yazid就说这
个子区间是"新生舞会的"。所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个
，我们规定值最小的数为众数。现在，Yazid想知道，共有多少个子区间是"新生舞会的"
Input
第一行2个用空格隔开的非负整数n,type，表示序列的长度和数据类型。数据类型的作用将在子任务中说明。
第二行n个用空格隔开的非负整数，依次为A1,A2,...,An，描述这个序列。
N<=500000,0<=Type<=3
对于所有数据，保证 0 ≤ Ai ≤ n - 1。
对于 type = 0 的数据，没有任何特殊约定。
对于 type = 1 的数据，保证 Ai ∈ {0, 1}。
对于 type = 2 的数据，保证序列 A 的众数在整个序列中的出现次数不超过 15。
对于 type = 3 的数据，保证 Ai ≤ 7。
Output
输出一行一个整数，表示答案。
枚举众数的值a，一个区间(L,R]符合条件，当且仅当F(R)-F(L)>0,其中F(x)=2*([1,x]中a的个数)-x。
从左到右扫描x=1..n，插入F(x)，查询F(<x)的和
F(x)在跨过a的出现位置时发生突变，其余时候x每+1，F(x)就-1，因此可以批量处理，每次插入和查询一个区间，算一下贡献可以转为区间加二次函数，单点查询，可以用树状数组维护
时间复杂度O(nlogn)
#include<bits/stdc++.h>
typedef long long i64;
const int N=5e5+;
char ib[N*],*ip=ib;
int _(){int x;scanf("%d",&x);return x;}
i64 ans=;
int n,mx;
struct pos{
int x,y;
}ps[N],pb[N];
void rsort(pos*a,pos*b,int n){
for(int t=;t<;t+=){
int ts[]={};
pos*rs[],*p=b;
for(int i=;i<n;++i)++ts[a[i].y>>t&];
for(int i=;i<;++i)rs[i]=p,p+=ts[i];
for(int i=;i<n;++i)*rs[a[i].y>>t&]++=a[i];
std::swap(a,b);
}
}
int tk;
struct node{
i64 s0,s1,s2;
int ed;
}bit[N*];
void inc(int w,int a){
w+=n+;
i64 a0=a*w*i64(w-),a1=a*i64(-w*),a2=a;
for(;w<=mx;w+=w&-w){
if(bit[w].ed!=tk){
bit[w]=(node){a0,a1,a2,tk};
}else{
bit[w].s0+=a0;
bit[w].s1+=a1;
bit[w].s2+=a2;
}
}
}
i64 sum(int w){
w+=n+;
int w0=w;
i64 s0=,s1=,s2=;
for(;w;w-=w&-w)if(bit[w].ed==tk){
s0+=bit[w].s0;
s1+=bit[w].s1;
s2+=bit[w].s2;
}
return (s2*w0+s1)*w0+s0;
}
void ins(int l,int r,int c){
inc(*c-r+,);
inc(*c-l+,-);
}
void que(int l,int r,int c){
ans+=sum(*c-l)-sum(*c-r);
}
void cal(pos*a,int n){
++tk;
ins(,a[].x,);
for(int i=;i<n;++i){
int w=a[i].x;
que(a[i].x,a[i+].x,i);
ins(a[i].x,a[i+].x,i);
}
que(a[n].x,::n+,n);
}
int main(){
n=_();_();
mx=n*+;
for(int i=;i<=n;++i)ps[i]=(pos){i,_()};
rsort(ps+,pb,n);
for(int i=,j=;i<=n;i=j){
for(++j;j<=n&&ps[i].y==ps[j].y;++j);
cal(ps+i-,j-i);
}
printf("%lld\n",ans/);
return ;
}