洛谷P4168 题意：求区间l到r的众数 强制在线
思路：分块 考虑维护什么：
对于整块 希望直接得到众数及其出现的次数
对于零散处 暴力求出每个数出现次数 但还要知道它们在整块中的出现次数 来更新答案
维护两个要预处理的数组：ans表示块与块之间的众数是什么 sum表示某个数在某一块之前出现的次数
O(n*sqrt(n))预处理
细节：要离散化 用桶来记录比较出现次数 要记得还原
#include<bits/stdc++.h>
using namespace std;
#define N 40005
int num[N],pos[N],t[N],sum[N][205],a[N],b[N],ans[205][205],sta[205],end[205];
int solve(int l,int r)
{
int p=pos[l],q=pos[r];
if(p==q){//如果在同一个块中 就暴力for
int now=0;
for(int i=l;i<=r;i++){
t[num[i]]++;
if(t[num[i]]>t[now]||(t[num[i]]==t[now]&&now>num[i])) now=num[i];
}
for(int i=l;i<=r;i++) t[num[i]]=0;//每次记得还原
return b[now];
}//for(int i=0;i<=6;i++) printf("t:%d ",t[i]);
int now=ans[p+1][q-1];//printf("la: %d
",now);
t[now]+=sum[now][q-1]-sum[now][p];//初始化整块之间的众数及其出现次数
for(int i=l;i<=end[p];i++){//同样用桶去比较
if(!t[num[i]]) t[num[i]]+=sum[num[i]][q-1]-sum[num[i]][p];
t[num[i]]++;
if(t[num[i]]>t[now]||(t[num[i]]==t[now]&&now>num[i])) now=num[i];
}
for(int i=sta[q];i<=r;i++){
if(!t[num[i]]) t[num[i]]+=sum[num[i]][q-1]-sum[num[i]][p];
t[num[i]]++;
if(t[num[i]]>t[now]||(t[num[i]]==t[now]&&now>num[i])) now=num[i];
}//最后记得所有的清空
t[ans[p+1][q-1]]=0;
for(int i=l;i<=end[p];i++) t[num[i]]=0;
for(int i=sta[q];i<=r;i++) t[num[i]]=0;
return b[now];
}
int main()
{
int n,m,block,x,y,last=0;
scanf("%d%d",&n,&m);
block=(int)sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]),b[i]=a[i];//离散化 a是原数组 b是用来排序二分的数组
//为什么是这样求呢：若不能整除 相当于除完+1 能整除 又可以防止多+1
pos[i]=(i+block-1)/block;//pos是i所在块的位置 注意求法！！
if(!sta[pos[i]]) sta[pos[i]]=i;//sta end是一个块的起始和终止位置
end[pos[i]]=i;
}
sort(b+1,b+1+n);
int l=unique(b+1,b+1+n)-b-1;//l存的是离散化后数的个数 其实是数的种类数
//注意一定是b+1+l!! 因为去重后b的元素是l
for(int i=1;i<=n;i++) num[i]=lower_bound(b+1,b+1+l,a[i])-b;//num存离散化后每一个数的排位
//预处理块与块间的众数是哪个
for(int i=1;i<=pos[n];i++){
int now=0;//now临时记录众数是谁 t是桶 记录每一个数出现次数
for(int j=sta[i];j<=n;j++){//枚举的是从这个块起始位置向后的所有位置
t[num[j]]++;
if(t[now]<t[num[j]]||(t[now]==t[num[j]]&&now>num[j])) now=num[j];//数较小也要更新
ans[i][pos[j]]=now;
}
for(int j=sta[i];j<=n;j++) t[num[j]]=0;//每次用完要记得还原！！
}
//预处理每一个数在每一个块中出现的次数
for(int i=1;i<=n;i++) sum[num[i]][pos[i]]++;
for(int i=1;i<=l;i++)//边界是l！！是因为枚举的是不同种类的数
for(int j=1;j<=pos[n];j++)//枚举每一块
sum[i][j]+=sum[i][j-1];//数的出现次数满足加减性 这一块由它本身和它前一块的出现次数累加得来
while(m--)
{
scanf("%d%d",&x,&y);
x=(x+last-1)%n+1,y=(y+last-1)%n+1;
if(x>y) swap(x,y);
last=solve(x,y);
printf("%d
",last);
}
}
/*
6 3
1 2 3 2 1 2
1 5
3 6
1 5
*/