题意
静态区间求众数（出现次数相同输出值较小的，(n leq 4e4) , (q leq 5e4)），强制在线
思路
由于n比较小，但是直接(n^2)又过不了，众数这个信息又不好用log数据结构维护（不容易合并两区间），所以考虑根号数据结构，离线静态区间众数可以用莫队完成啦，但是由于这道题强制在线，所以我们考虑分块做法
即使是分块也无法简单的合并两个块的数据，所以我们考虑分块的本质—— 暴力，直接维护块合并后的信息
-
用(f[i][j])表示第i块到第j块这一段的众数，那么接下来就可以只考虑怎么加入两头的数
-
考虑暴力求众数的做法：记录当前的众数以及所有数的出现次数，如果新加入的数的出现次数大于众数，那么它取代原众数成为新的众数
-
改进暴力做法。同样，我们每次询问开了一个桶存众数的出现次数，但问题是我们不能暴力加每一个数，所以我们还要知道第i个块到第j个块这一段中每一个数的出现次数，于是我们要开一个三维数组[i][j][k]，这样显然会爆内存，改进方法显然就是前缀和，用sum[i][k]表示存了前i块数据的桶即可
-
查询一个区间，我们要先读取i到j块的桶，但暴力每个数都读取仍旧会(O(n))超时，所以我们考虑哪一些不可能成为众数，就不读取它的桶，思考发现除了f[i][j]之外可能成为众数的只有边角上出现了的数，只读取它们的桶就可以做到(sqrt{n})
总结思路：预处理出f,sum两个数组，大块直接调取f[i][j]，边角先从sum中读取桶再按照暴力方法直接加数
Code：
#include<bits/stdc++.h>
#define N 40005
#define S 205
using namespace std;
int n,m,x=0,a[N];
int size,cnt,sum[S][N],f[S][S];
int L[S],R[S],pos[N],tng[N];
int b[N],len;
template <class T>
inline void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
inline int get_lit(int x) { return lower_bound(b+1,b+len+1,x)-b; }
void init()
{
sort(b+1,b+n+1);
len=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i) a[i]=get_lit(a[i]);
int hfu=0;//丑陋的分块
for(int i=1;i<=n;++i)
{
if(!hfu) L[++cnt]=i;
++hfu;
pos[i]=cnt;
if(hfu==size||i==n) R[cnt]=i,hfu=0;
}
for(int i=1;i<=n;++i)
{
if(pos[i]!=pos[i-1]) memcpy(sum[pos[i]],sum[pos[i-1]],sizeof(sum[pos[i-1]]));
sum[pos[i]][a[i]]++;
}
for(int i=1;i<=cnt;++i)
{
int mode=0,lsw=i;
memset(tng,0,sizeof(tng));
for(int j=L[i];j<=n;++j)
{
++tng[a[j]];
if((tng[mode]<tng[a[j]])||(tng[mode]==tng[a[j]]&&a[j]<mode)) mode=a[j];
if(j==R[lsw]) f[i][lsw++]=mode;
}
}
}
inline int query(int l,int r)
{
int lp=pos[l],rp=pos[r];
if(lp==rp)//直接暴力
{
int mode=0;
for(int i=l;i<=r;++i)
{
++tng[a[i]];
if((tng[mode]<tng[a[i]])||(tng[mode]==tng[a[i]]&&a[i]<mode)) mode=a[i];
}
for(int i=l;i<=r;++i) --tng[a[i]]; //还原tng数组
return mode;
}
int mode=f[lp+1][rp-1];
tng[mode]+=sum[rp-1][mode]-sum[lp][mode];
for(int i=l;i<=R[lp];++i)
{
if(!tng[a[i]]) tng[a[i]]+=(sum[rp-1][a[i]]-sum[lp][a[i]]);
++tng[a[i]];
if((tng[mode]<tng[a[i]])||(tng[mode]==tng[a[i]]&&a[i]<mode)) mode=a[i];
}
for(int i=L[rp];i<=r;++i)
{
if(!tng[a[i]]) tng[a[i]]+=(sum[rp-1][a[i]]-sum[lp][a[i]]);
++tng[a[i]];
if((tng[mode]<tng[a[i]])||(tng[mode]==tng[a[i]]&&a[i]<mode)) mode=a[i];
}
for(int i=l;i<=R[lp];++i) tng[a[i]]=0;
for(int i=L[rp];i<=r;++i) tng[a[i]]=0;
tng[f[lp+1][rp-1]]=0;
return mode;
}
int main()
{
read(n);read(m);
size=sqrt(n);
for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
init();
memset(tng,0,sizeof(tng));
while(m--)
{
int l,r;
read(l);read(r);
l=(l+x-1)%n+1;
r=(r+x-1)%n+1;
if(l>r) swap(l,r);
x=b[query(l,r)];
printf("%d
",x);
}
return 0;
}
这道题与其说是分块不如说是一道模拟题，按照暴力思路直接优化就不难得到正解