谨以此文纪念一场灾难
来给这位善良的人的人点点赞
题面
题解：
首先 题面中所指的众数为 绝对众数（绝对众数是指在一组数据中出现次数 \(超过\) 总数一半的数值。）， 下文的所有众数也指绝对众数。
有以下性质
-
任意一个区间的绝对众数的数值唯一
-
如果\(x\)是区间\([l,r]\)的众数，那么对于\(l≤k≤r\)，\(x\)一定是区间\([l,k]\)或区间\((k,r]\)的众数。
-
以 \(n\) 结尾的所有区间的绝对众数构成的集合大小不超过为 \(logn\)
一 ( \(O(nlog^{2}n)\) 做法) ：
因为众数个数的取值范围极小，且又有性质二可以利用，考虑分治做法：
对于每个区间 \([L,R]\) ,取 \(mid=(l+r)/2\) ,并将\(mid\) 设为性质二中的\(k\),以此求出所有可能的众数,并记录.
对于每个过 \(mid\) 的小区间 \([l,r]\) ,只有当存在众数 \(v\) 使得 \([l,r]\) 间的 \(sum_{v}\gt\frac{r-l+1}{2}\) ,才可使\(ans++\).
又因为C++中自动向下取整 ，所以对 \(r-l+1\) 的奇偶性分讨 得
\[sum_{v}\gt \lfloor\frac{r-l+1}{2} \rfloor\Leftrightarrow 2sum_{v}\ge r-l+2 \]设\(v\)在\([l,mid]\)的个数为 \(Sl\) ，\([mid+1,r]\) 为 \(Sr\)。
因为 \(sum_{v}=Sl+Sr\).
所以
所以对于每个\([L,R]\)中的\(l,r\)都有一一对应的\(l+2Sl,r-2Sr\).
因此可以预先处理出每个\(l\) 对应的$l+2Sl $ 值， 并储存起来。
然后对于每个\(r\),找出所有找出满足\((1)\) 的 \(l\)的个数（用求后缀的方式）,并计入\(ans\).
最后向下一层递归，本题就结束了.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+10;
int a[maxn],cnt[maxn],num[maxn],pos[maxn],c[maxn];
"""
cnt[]表示 值为l+Sl的个数
"""
int ans=0;
void sol(int l,int r)
{
if(l==r)
{
ans++;
return;
}
int mid=(l+r)>>1;
sol(l,mid);
sol(mid+1,r);
for(int i=l;i<=mid;++i)
if(++cnt[a[i]]>=(mid-i+1)/2 and !pos[a[i]])
num[pos[a[i]]=++num[0]]=a[i];
for(int i=l;i<=mid;++i)
cnt[a[i]]=0;
for(int i=mid+1;i<=r;++i)
if(++cnt[a[i]]>=(i-mid)/2 and !pos[a[i]])
num[pos[a[i]]=++num[0]]=a[i];
for(int i=l;i<=r;++i)
cnt[a[i]]=pos[a[i]]=0;
for(int j=1,v;v=num[j],j<=num[0];++j)
{
int L=1e9,R=0;
for(int i=mid,t=0;i>=l;--i)
{
if(a[i]==v)t+=2;
++c[t+i];
L=min(L,t+i);
R=max(R,t+i);
}
for(int i=R;i>=L;--i)
c[i]+=c[i+1];
int tmp=0;
for(int i=mid+1,t=0;i<=r;++i)
{
if(a[i]==v)t+=2;
tmp+=c[max(L,i-t+2)];
}
ans+=tmp;
for(int i=L;i<=R;++i)
c[i]=0;
}
num[0]=0;
}
signed main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
int n,x;
cin>>n;
cin>>x;
for(int i=1;i<=n;++i) cin>>a[i];
sol(1,n);
cout<<ans;
return 0;
}