正文
我与你无冤无仇，为何拿Ynoi做例题
分块，顾名思义就是分块，这是接触根号复杂度的开端
将要进行维护的东西分成 (sqrt{n}) 段
en，然后分别进行维护
直接拿例题开讲
P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III
典型的区间求众数题，不过这道题要求我们输出众数出现的个数而不是众数它本身
因为众数不具有区间可加性，所以线段树维护啥的就变得困难
考虑分块
我们将数列分成 (sqrt{n}) 段，预处理出第 (i) 到 (j) 段的众数，并将每个数出现的次数记录下来
然后就开始进行查询
-
如果 (l,r) 在同一块里，暴力统计
-
如果不在同一块里，左右边界分别暴力统计
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define N 500001
#define M 708
#define R register int
int n,m,v[N],ql,qr,st[N],discn,cnt[N],apr[M][M],ans,l[M],r[M],to[N],sz,szl[N],bfl,bfr;
std::vector<int>aprp[N];
inline void read(int &x){
x=0;
int w=1,ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
x*=w;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline int max(int a,int b) {return a>b?a:b;}
signed main(){
read(n),read(m);
for(R i=1;i<=n;++i) read(v[i]),st[i]=v[i];
std::sort(st+1,st+n+1);
discn=std::unique(st+1,st+n+1)-st-1;
for(R i=1;i<=n;++i){
v[i]=std::lower_bound(st+1,st+discn+1,v[i])-st;
aprp[v[i]].push_back(i);
szl[i]=aprp[v[i]].size()-1;
}
sz=(n-1)/M+1;
for(R i=1;i<=sz;++i){
l[i]=r[i-1]+1;r[i]=i*M;
for(R o=l[i];o<=r[i]&&o<=n;++o) to[o]=i;
}
r[sz]=n;
for(R i=2;i<sz;++i){
for(R o=i;o<sz;++o){
int &rs=apr[i][o];
rs=apr[i][o-1];
for(R p=l[o];p<=r[o];++p)
rs=max(rs,++cnt[v[p]]);
}
memset(cnt,0,sizeof(cnt));
}
while(m--){
read(ql),read(qr);
ql^=ans,qr^=ans;ans=0;
bfl=to[ql],bfr=to[qr];
if(bfl==bfr){
for(R i=ql;i<=qr;++i) ans=max(ans,++cnt[v[i]]);
for(R i=ql;i<=qr;++i) cnt[v[i]]=0;
}
else{
ans=apr[bfl+1][bfr-1];
for(R i=ql;i<=r[bfl];++i)
while(szl[i]+ans<aprp[v[i]].size()&&aprp[v[i]][szl[i]+ans]<=qr) ans++;
for(R i=qr;i>=l[bfr];--i)
while(szl[i]-ans>=0&&aprp[v[i]][szl[i]-ans]>=ql) ans++;
}
write(ans);putchar('
');
}
return 0;
}