发现写算法专题老是写不动，，，，
所以就先把我在luogu上的题解搬过来吧！
题目大意：查询区间众数，无修改，强制在线
乍一看是一道恐怖的题，仔细一看发现并没有那么难；
大致思路是这样的，首先我们要充分发挥分块暴力大法好的精神
先暴力预处理出每个块内每种蒲公英的个数，
然后求出对每个块而言的前缀和，
于是这样我们就可以区间查询任意两个块之间每种蒲公英的数量了
然后我们预处理出任意两个块之间的众数
最后对于每组询问，我们先找到夹在它们中间的块，
如果这个两个块r-l<=1，那么我们暴力求众数
为什么？ 因为不这样的话，万一x,y在一个快，那么r可能会比l小，要特判
如果x,y隔得很近，同样有各种奇奇怪怪的情况要做特判，
那既然这么麻烦，我们不如直接暴力搞是吧。
如果两个块相差超过了1，那么我们先取出中间块的众数，作为我们的answer，然后对旁边两个块暴力处理众数（此处注意判断时要加上中间的蒲公英）。
最后我们就得到了答案，
但是注意到ai的范围很大，所以我们需要离散化。
并且由于数量相同时要优先编号小的，于是我们处理众数的时候要多加这个判断
基本就是这样了。。。
表示本蒟蒻一A过了还是很开心的(^▽^)（虽然说第一次交没删调试结果too many or too few lines 了，但是去掉调试就过了，也可以算是一A嘛是吧）
下面代码：
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 40100
#define ac 210
#define D printf("line in %d\n",__LINE__);
int block,n,m,answer,tot;
int s[AC];
struct abc{
int num,w,x;
}b[AC];//原数列+离散化后数组
int sum[ac][AC];//每种数字块内前缀和
int ans[ac][ac];//任意两块之间的众数
int belong[AC];//所属块
int color[AC]; inline int read()
{
int x=;char c=getchar();
while(c>'' || c<'') c=getchar();
while(c>='' && c<='') x=x*+c-'',c=getchar();
return x;
} bool cmp1(abc a,abc b)
{
return a.w < b.w;
} bool cmp2(abc a,abc b)
{
return a.num < b.num;
} void search(int x,int y)
{
// printf("%d %d\n",x,y);
int l=x/block + ,r=y/block - ;//取出中间块
if(r - l <= )//如果x,y相差很小,那么暴力统计
{
answer=;
for(R i=x;i<=y;i++)
if((++color[b[i].x] > color[answer]) || (color[b[i].x] == color[answer] && b[i].x < answer)) answer=b[i].x;
for(R i=x;i<=y;i++)
--color[b[i].x];
printf("%d\n",s[answer]);
return ;
}
else//不然的话
{
int ll=l * block - ,rr=(r+) * block;
answer=ans[l][r];
for(R i=x;i<=ll;i++)
{
++color[b[i].x];
if(color[b[i].x] + sum[r][b[i].x] - sum[l-][b[i].x] > color[answer] + sum[r][answer] - sum[l-][answer]) answer=b[i].x;
else if(color[b[i].x] + sum[r][b[i].x] - sum[l-][b[i].x] == color[answer] + sum[r][answer] - sum[l-][answer] && b[i].x < answer) answer=b[i].x;//编号小也要优先，因为一行写不下，为了美观，，，就用else吧，不然就用||了
}
for(R i=rr;i<=y;i++)
{
++color[b[i].x];
if(color[b[i].x] + sum[r][b[i].x] - sum[l-][b[i].x] > color[answer] + sum[r][answer] - sum[l-][answer]) answer=b[i].x;
else if(color[b[i].x] + sum[r][b[i].x] - sum[l-][b[i].x] == color[answer] + sum[r][answer] - sum[l-][answer] && b[i].x < answer) answer=b[i].x;
}
for(R i=x;i<=ll;i++) --color[b[i].x];
for(R i=rr;i<=y;i++) --color[b[i].x];
printf("%d\n",s[answer]);
return ;
}
} void pre()//读入
{
n=read(),m=read();
block=sqrt(n);
for(R i=;i<=n;i++) b[i].w=read(),b[i].num=i;
sort(b+,b+n+,cmp1);
for(R i=;i<=n;i++)
{
if(b[i].w != b[i-].w)
{
s[++tot]=b[i].w;//存下对应新编号的对应真实编号
b[i].x=tot;
}
else b[i].x=b[i-].x;//离散化
}
sort(b+,b+n+,cmp2);
} void getsum()
{//注意0也被分在块0中
for(R i=;i<=n;i++)
{
belong[i]=i/block;
sum[belong[i]][b[i].x]++;
}
for(R i=;i<=belong[n];i++)
for(R j=;j<=tot;j++)
sum[i][j]+=sum[i-][j];
} void getans()
{
for(R i=;i<=belong[n];i++)
{
int be=i * block,now=;
if(!be) be=;//这里和作诗不同，因为这里的now要参与比较了，而不是单纯的统计，而now初始值为0，所以color[0]不能被修改
for(R j=be;j<=n;j++)
{
if((++color[b[j].x] > color[now]) || (color[b[j].x] == color[now] && b[j].x < now)) now=b[j].x;//更新ans
ans[i][belong[j]]=now;//存下新ans
}
for(R j=be;j<=n;j++) --color[b[j].x];//暴力撤销
}
/*for(R i=0;i<=belong[n];i++)
{
for(R j=i;j<=belong[n];j++)
printf("%d ",ans[i][j]);
printf("\n");
}*/
} void work()//预处理出前缀和和众数
{
int a,b;
for(R i=;i<=m;i++)
{
a=(read() + s[answer] -) % n + ,b=(read() + s[answer] - ) % n + ;//获取询问
if(a < b) search(a,b);
else search(b,a);//因为经过了运算，所以大小顺序就可能改变了
}
} int main()
{
// freopen("in.in","r",stdin);
pre();
getsum();
getans();
work();
// fclose(stdin);
return ;
}