我好弱啊。。这题调了2天QwQ
题目大意：给定一个长度为n（n<=40000）的序列，m（m<=50000）次询问l~r之间出现次数最多的数。（区间众数）
这题如果用主席树就可以不用处理一堆前缀和。。蓝鹅我不会~T_T~
把序列n分成sqrt(n)块，先把所有数离散化，预处理出poi[i][j]表示第i块到第j块的众数（即出现次数最多的数）。
询问有两种情况:
第一种情况是l~r在某个块中，那么直接扫一遍求出众数，效率O(sqrt(n))。
第二种情况是l~r在多个块中，l在x块，r在y块，那么我们可以把它分为三部分：①l~x块最后一个数②x+1块~y-1块③y块第一个数~r。
因为我们求出了poi数组，所以我们可以知道第二部分的众数，显然我们只要统计一下第一部分、第三部分每个数出现的次数，将它们和第二部分的众数出现的次数进行比较，出现次数最多的数就是l~r的众数。
而第一部分、第三部分数的个数不超过2*sqrtn(n)个，所以扫一遍第一部分、第三部分的数，效率O(sqrt(n))，问题就是怎么O(1)求出第一部分、第三部分的每个数在l~r出现的次数了。如果是O(1)，那么可以想到的就是前缀和，于是我们再预处理出qzh[i][a]表示前i块中a出现的次数，qzh2[i][j][a]表示第i块前j个数中a出现的次数。那么设第一部分某个数为a，l在x块，r在y块，它在l~r中出现的次数就是:
qzh[y-1][a]-qzh[x-1][a]-qzh2[x][(l-1)%sqrtn==0?sqrtn:(l-1)%sqrtn][a]
+qzh2[x][(r-1)%sqrtn+1==sqrtn?0:(r-1)%sqrtn+1][a]
【写的好丑哇QAAAAQ
第三部分同理，然后和第二部分预处理出来的众数在l~r出现的次数（求法同理）比较找出最大的就行了。
预处理O(nsqrt(n))，询问O(qsqrt(n))，总的时间复杂度O((n+q)sqrt(n))。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
map<int,int>M[];
struct zs{int num,pos;}b[];
int n,m,l,r,cnt,ans,poi[][],a[],pos[],sum[],qzh[][],qzh2[][][],num[],ppos[][];
bool v[];
bool cmp(zs a,zs b){return a.num<b.num;}
int main()
{
scanf("%d %d",&n,&m);
int sqrtn=(int)ceil(sqrt(n));
for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i].num=a[i],b[i].pos=i;
sort(b+,b++n,cmp);
for(int i=;i<=n;i++)
{
if(b[i].num!=b[i-].num)cnt++;
pos[b[i].pos]=cnt;
}
for(int i=;i<=sqrtn;i++)
for(int j=;j<=sqrtn;j++)
{
if((i-)*sqrtn+j<=n)if(M[i].find(a[(i-)*sqrtn+j])==M[i].end())
M[i][a[(i-)*sqrtn+j]]=++num[i];
ppos[i][pos[(i-)*sqrtn+j]]=M[i][a[(i-)*sqrtn+j]];
}
for(int i=;i<=n;i++)qzh[((i-)/sqrtn)+][pos[i]]++;
for(int i=;i<=n;i++)for(int j=;j<=sqrtn;j++)qzh[j][i]+=qzh[j-][i];
for(int i=;i<=sqrtn;i++)for(int j=;j<=sqrtn;j++)if((i-)*sqrtn+j<=n)qzh2[i][j][ppos[i][pos[(i-)*sqrtn+j]]]++;
for(int i=;i<=sqrtn;i++)
{
for(int k=;k<=sqrtn;k++)if((i-)*sqrtn+k<=n)v[pos[(i-)*sqrtn+k]]=;
for(int k=;k<=sqrtn;k++)
if((i-)*sqrtn+k<=n)
if(!v[pos[(i-)*sqrtn+k]])
{
for(int j=;j<=sqrtn;j++)
if((i-)*sqrtn+j<=n)qzh2[i][j][ppos[i][pos[(i-)*sqrtn+k]]]+=qzh2[i][j-][ppos[i][pos[(i-)*sqrtn+k]]];
v[pos[(i-)*sqrtn+k]]=;
}
}
for(int i=;i<=sqrtn;i++)
{
memset(sum,,sizeof(sum));
int max=,maxi=;
for(int j=i;j<=sqrtn;j++)
{
for(int k=;k<=sqrtn;k++)
{
int x=(j-)*sqrtn+k;
if(x>n)break;
if(++sum[pos[x]]>max||((sum[pos[x]]==max)&&(pos[x]<pos[maxi])))max=sum[pos[x]],maxi=x;
}
poi[i][j]=maxi;
}
}
for(int i=;i<=m;i++)
{
scanf("%d %d",&l,&r);
l=(l+ans-)%n+;r=(r+ans-)%n+;if(r<l)swap(l,r);
if((int)ceil(r/sqrtn)==(int)ceil(l/sqrtn))
{
int maxx=,maxi=;
memset(sum,,sizeof(sum));
for(int j=l;j<=r;j++)
if(++sum[pos[j]]>maxx||((sum[pos[j]]==maxx)&&(pos[j]<pos[maxi])))maxx=sum[pos[j]],maxi=j;
ans=a[maxi];
printf("%d\n",a[maxi]);
}else
{
int ll=-,rr=;
for(int j=;j<=sqrtn;j++)
{
if(j*sqrtn+>=l&&(ll==-))ll=j*sqrtn;
if(j*sqrtn<=r)rr=j*sqrtn;
}
int y=poi[ll/sqrtn+][rr/sqrtn];
for(int j=l;j<=ll;j++)
{
int lll=y;
int x=qzh[rr/sqrtn][pos[j]]-qzh[max(ll/sqrtn-,)][pos[j]]-qzh2[ll/sqrtn][(l-)%sqrtn==?sqrtn:(l-)%sqrtn][ppos[ll/sqrtn][pos[j]]]+qzh2[rr/sqrtn+][(r-)%sqrtn+==sqrtn?:(r-)%sqrtn+][ppos[rr/sqrtn+][pos[j]]];
y=qzh[rr/sqrtn][pos[lll]]-qzh[max(ll/sqrtn-,)][pos[lll]]-qzh2[ll/sqrtn][(l-)%sqrtn==?sqrtn:(l-)%sqrtn][ppos[ll/sqrtn][pos[lll]]]+qzh2[rr/sqrtn+][(r-)%sqrtn+==sqrtn?:(r-)%sqrtn+][ppos[rr/sqrtn+][pos[lll]]];
if(x>y||((x==y)&&pos[j]<pos[lll]))y=j;else y=lll;
}
for(int j=rr+;j<=r;j++)
{
int lll=y;
int x=qzh[rr/sqrtn][pos[j]]-qzh[max(ll/sqrtn-,)][pos[j]]-qzh2[ll/sqrtn][(l-)%sqrtn==?sqrtn:(l-)%sqrtn][ppos[ll/sqrtn][pos[j]]]+qzh2[rr/sqrtn+][(r-)%sqrtn+==sqrtn?:(r-)%sqrtn+][ppos[rr/sqrtn+][pos[j]]];
y=qzh[rr/sqrtn][pos[lll]]-qzh[max(ll/sqrtn-,)][pos[lll]]-qzh2[ll/sqrtn][(l-)%sqrtn==?sqrtn:(l-)%sqrtn][ppos[ll/sqrtn][pos[lll]]]+qzh2[rr/sqrtn+][(r-)%sqrtn+==sqrtn?:(r-)%sqrtn+][ppos[rr/sqrtn+][pos[lll]]];
if(x>y||((x==y)&&pos[j]<pos[lll]))y=j;else y=lll;
}
printf("%d\n",a[y]);ans=a[y];
}
}
}