题意
长为 \(n\) 的序列，询问区间众数，强制在线。
\(n\leq 5\times 10^5\).
分析
-
考虑分块，暴力统计出整块到整块之间的众数次数。
-
然后答案还可能出现在两边的两个独立的块中，开 \(vector\) 记录每种数字出现的位置集合，然后暴力判断两边两个块中的元素出现的次数。发现并不需要知道具体在 \([l,r]\) 内出现了多少次，而只需要知道 \([l,r]\) 中是否有 \(ans+1\)个该种颜色。
-
总时间复杂度为 \(O(n\sqrt n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long long LL;
inline int gi(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=5e5 + 7,M=720;
int n,m,len,sz,tp;
int V[N],bl[N],a[N],p[N],cnt[N],f[M][M],st[N],vc[N];
int L(int x){return (x-1)*sz+1;}
int R(int x){return min(n,x*sz);}
vector<int>pos[N];
int solve(int l,int r){
int res=0;
if(bl[l]==bl[r]){
for(int i=l;i<=r;++i){
st[++tp]=a[i];
Max(res,++cnt[a[i]]);
}
for(;tp;--tp) cnt[st[tp]]=0;
return res;
}
res=f[bl[l]+1][bl[r]-1];
for(int i=R(bl[l]);i>=l;--i){
int x=p[i],y=x+res;
if(y<vc[a[i]]&&pos[a[i]][y]<=r) ++res;
}
for(int i=L(bl[r]);i<=r;++i){
int y=p[i],x=y-res;
if(x>=0&&pos[a[i]][x]>=l) ++res;
}
return res;
}
int main(){
n=gi(),m=gi();sz=sqrt(n);
rep(i,1,n) a[i]=gi(),bl[i]=(i-1)/sz+1,V[i]=a[i];sort(V+1,V+1+n);
len=unique(V+1,V+1+n)-V-1;
rep(i,1,n) a[i]=lower_bound(V+1,V+1+len,a[i])-V,pos[a[i]].pb(i),p[i]=pos[a[i]].size()-1;
rep(i,1,len) vc[i]=pos[i].size();
for(int p=1;p<=bl[n];++p){
int tmp=0,tp=0;
for(int i=L(p);i<=n;++i){
Max(tmp,++cnt[a[i]]);
st[++tp]=a[i];
if(i%sz==0) f[p][bl[i]]=tmp;
}
for(;tp;--tp) cnt[st[tp]]=0;
}
int lastans=0;
while(m--){
int l=gi()^lastans,r=gi()^lastans;
if(l>r) swap(l,r);
printf("%d\n",lastans=solve(l,r));
}
return 0;
}
