Description
Input
修正一下
l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1
Output
Sample Input
6 3
1 2 3 2 1 2
1 5
3 6
1 5
Sample Output
1
2
1
HINT
修正下：
n <= 40000, m <= 50000
Solution
考虑分块，存两个东西，一个是两个块之间包含的区间的答案，另一个块的每个蒲公英的出现次数的前缀和
之前还要离散化
询问的时候就只要走边角料就可以了，访问一种蒲公英的出现次数用前缀和作差就好了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=40000+10,MAXM=200+10;
int n,m,a[MAXN],sum[MAXM][MAXN],id[MAXM][MAXM],P[MAXN],vis[MAXN],st[MAXM],ed[MAXM],cnt,lastans,unit,bel[MAXN];
std::vector<int> V;
std::map<int,int> M;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void discretization()
{
REP(i,1,n)V.push_back(a[i]);
std::sort(V.begin(),V.end());
V.erase(std::unique(V.begin(),V.end()),V.end());
REP(i,0,V.size()-1)M[V[i]]=i+1,P[i+1]=V[i];
REP(i,1,n)a[i]=M[a[i]];
}
inline void init()
{
unit=std::sqrt(n);
REP(i,1,n)bel[i]=(i-1)/unit+1;
for(register int i=1;i<=n;i+=unit)st[++cnt]=i,ed[cnt]=min(i+unit-1,n);
REP(i,1,cnt)
{
REP(j,1,n)sum[i][j]=sum[i-1][j];
REP(j,st[i],ed[i])sum[i][a[j]]++;
}
REP(i,1,cnt)
{
int app=0,res=0;
REP(j,i,cnt)
{
REP(k,st[j],ed[j])
{
vis[a[k]]++;
if(vis[a[k]]==app)chkmin(res,a[k]);
else if(vis[a[k]]>app)app=vis[a[k]],res=a[k];
}
id[i][j]=res;
}
REP(j,st[i],n)vis[a[j]]--;
}
}
inline int solve(int l,int r)
{
int app=0,res=0;
if(bel[r]-bel[l]<=1)
{
REP(i,l,r)
{
vis[a[i]]++;
if(vis[a[i]]==app)chkmin(res,a[i]);
else if(vis[a[i]]>app)app=vis[a[i]],res=a[i];
}
REP(i,l,r)vis[a[i]]--;
return res;
}
res=id[bel[l]+1][bel[r]-1];
app=sum[bel[r]-1][res]-sum[bel[l]][res];
DEP(i,ed[bel[l]],l)
{
vis[a[i]]++;
int all=sum[bel[r]-1][a[i]]-sum[bel[l]][a[i]]+vis[a[i]];
if(all==app)chkmin(res,a[i]);
else if(all>app)app=all,res=a[i];
}
REP(i,st[bel[r]],r)
{
vis[a[i]]++;
int all=sum[bel[r]-1][a[i]]-sum[bel[l]][a[i]]+vis[a[i]];
if(all==app)chkmin(res,a[i]);
else if(all>app)app=all,res=a[i];
}
DEP(i,ed[bel[l]],l)vis[a[i]]--;
REP(i,st[bel[r]],r)vis[a[i]]--;
return res;
}
int main()
{
read(n);read(m);
REP(i,1,n)read(a[i]);
discretization();
init();
while(m--)
{
int x,y,l,r;read(x);read(y);
l=(x+lastans-1)%n+1,r=(y+lastans-1)%n+1;
if(l>r)std::swap(l,r);
write(lastans=P[solve(l,r)],'\n');
}
return 0;
}