n<=500000的数字，问有多少个区间的众数出现次数严格大于区间长度的一半。
这么说来一个区间就一个众数了，所以第一反应是枚举数字，对下标进行处理。然后没有第二反应。很好。
在枚举一个数字的时候，可以把这个数字出现的位置记+1，没出现的位置记-1，实际就是问现在这个数组有多少个区间和>0，就是问对每个前缀和Si有多少Sj<Si。
出现的位置加起来总共只有n个，如果-1的那些区间能够进行区间处理该多好啊！
那就维护一个以Si的值为下标的东西，然后查一个区间的答案就是查：
红色部分。也就是要查一个区间和乘上若干，以及一个区间每个数乘上等差数列。可以通过维护每个Si的值的个数的区间和，以及区间Cnt_i * i的和。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
//#include<bitset>
#include<queue>
//#include<math.h>
//#include<time.h>
//#include<iostream>
using namespace std; int n,type;
#define maxn 1000011
#define LL long long
struct Node
{
int id,v;
bool operator < (const Node &b) const {return v<b.v || (v==b.v && id<b.id);}
}a[maxn];
int lisan[maxn],li=; const int most=;
struct SMT
{
struct Node
{
int ls,rs;
int sum;LL sss;
int add;
}a[maxn<<];
int size,root;
void clear() {size=root=;}
int ql,qr,v;
void up(int x)
{
const int &p=a[x].ls,&q=a[x].rs;
a[x].sum=a[p].sum+a[q].sum;
a[x].sss=a[p].sss+a[q].sss;
}
void New(int &x)
{
x=++size; a[x].ls=a[x].rs=;
a[x].sss=a[x].add=a[x].sum=;
}
void addsingle(int x,int L,int R,int v)
{
a[x].sum+=(R-L+)*v;
a[x].sss+=((1ll*(most-R++most-L+)*(R-L+))>>)*v;
a[x].add+=v;
}
void down(int x,int L,int R)
{
int &p=a[x].ls,&q=a[x].rs,mid=(L+R)>>;
if (!p) New(p); if (!q) New(q);
if (a[x].add)
{
addsingle(p,L,mid+,a[x].add);
addsingle(q,mid+,R,a[x].add);
a[x].add=;
}
}
void Add(int &x,int L,int R)
{
if (!x) New(x);
if (ql<=L && R<=qr) {addsingle(x,L,R,v); return;}
down(x,L,R);
const int mid=(L+R)>>;
if (ql<=mid) Add(a[x].ls,L,+mid);
if (qr> mid) Add(a[x].rs,mid+,R);
up(x);
}
void add(int L,int R,int v)
{
if (L>R) return;
L+=most>>; R+=most>>;
this->v=v; ql=L; qr=R;
Add(root,,most);
}
LL Querysum(int &x,int L,int R)
{
if (!x) New(x);
if (ql<=L && R<=qr) return a[x].sum;
down(x,L,R);
const int mid=(L+R)>>; LL ans=;
if (ql<=mid) ans+=Querysum(a[x].ls,L,mid);
if (qr> mid) ans+=Querysum(a[x].rs,mid+,R);
return ans;
}
LL querysum(int L,int R)
{
if (L>R) return ;
L+=most>>; R+=most>>;
ql=L; qr=R;
return Querysum(root,,most);
}
LL Querysss(int &x,int L,int R)
{
if (!x) New(x);
if (ql<=L && R<=qr) return a[x].sss;
down(x,L,R);
const int mid=(L+R)>>; LL ans=;
if (ql<=mid) ans+=Querysss(a[x].ls,L,mid);
if (qr> mid) ans+=Querysss(a[x].rs,mid+,R);
return ans;
}
LL querysss(int L,int R)
{
if (L>R) return ;
L+=most>>; R+=most>>;
ql=L; qr=R;
return Querysss(root,,most);
}
}t; int main()
{
scanf("%d%d",&n,&type);
for (int i=;i<=n;i++) scanf("%d",&a[i].v),a[i].id=i;
sort(a+,a++n); a[n+].v=0x3f3f3f3f; LL ans=;
for (int i=,j=;i<=n+;i++) if (a[i].v!=a[i-].v)
{
t.clear();
int last=,where=;
t.add(,,);
for (;j<i;j++)
{
const int now=a[j].id;
if (now-last>)
{
int len=now-last-;
ans+=t.querysss(where-len-,where-)+t.querysum(-(most>>),where-len-)*len
-t.querysum(where-len-,where-)*(most-where-(most>>)+);
t.add(where-len,where-,);
where-=len;
}
ans+=t.querysum(-(most>>),where);
where++; t.add(where,where,);
last=now;
}
int len=n-last;
(len)&&(ans+=t.querysss(where-len-,where-)+t.querysum(-(most>>),where-len-)*len
-t.querysum(where-len-,where-)*(most-where-(most>>)+));
}
printf("%lld\n",ans);
return ;
}
这题还有树状数组和分治的写法。待填坑。