WA80求条玄关

#include<bits/stdc++.h>
using namespace std;
const int N=40010;
int a[N],b[N];
int f[41][41][N];
int d[41][41];
int l[N],r[N];
int g[N];
int main()
{
	ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	int len=unique(b+1,b+n+1)-b;
	
	int m=min(n,1001);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+len+1,a[i])-b;
		//cout<<a[i]<<'\n';
		if(r[cnt]<i) 
		{
			l[++cnt]=i;
			r[cnt]=min(n,i+m-1);
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		for(int j=i;j<=cnt;j++)
		{
			for(int k=l[j];k<=r[j];k++)
			{
				f[i][j][a[k]]++;
			}
			for(int k=1;k<=n;k++)
			{
				f[i][j][k]+=f[i][j-1][k];
				if(f[i][j][k]>f[i][j][d[i][j]])
				{
					d[i][j]=k;
				}
			}
			//cout<<i<<' '<<j<<' '<<d[i][j]<<'\n';
		}
	}
	int preans=0;
	while(q--)
	{
		int ls,rs;
		cin>>ls>>rs;
		ls=(ls+preans-1)%n+1;
		rs=(rs+preans-1)%n+1;
	//	cout<<ls<<' '<<rs<<'\n';
		if(ls>rs) swap(ls,rs);
		int lb=cnt,rb=0;
		for(int i=1;i<=cnt;i++)
		{
			if(l[i]>=ls&&r[i]<=rs)
			{
				lb=min(lb,i);
				rb=max(rb,i);
			}
		}
		if(!rb)
		{
			int res=0;
			for(int i=ls;i<=rs;i++)
			{
				g[a[i]]++;
				if(g[a[i]]>g[res]||(a[i]<res&&g[a[i]]==g[res]))
				{
					res=a[i];
				}
			}
			for(int i=ls;i<=rs;i++)
			{
				g[a[i]]--;
			}
			cout<<b[res]<<'\n';
			preans=b[res];
			continue;
		}
		int p=d[lb][rb];
		for(int i=1;i<=cnt;i++)
		{
			if(l[i]>=ls&&r[i]<=rs) continue;
			else if(l[i]>=ls)
			{
				for(int j=l[i];j<=rs;j++)
				{
					f[lb][rb][a[j]]++;
					if(f[lb][rb][a[j]]>f[lb][rb][p]||(f[lb][rb][a[j]]==f[lb][rb][p]&&p>a[j]))
					{
						p=a[j];
					}
				}
				
			}
			else if(r[i]<=rs)
			{
				for(int j=r[i];j>=ls;j--)
				{
					f[lb][rb][a[j]]++;
					if(f[lb][rb][a[j]]>f[lb][rb][p]||(f[lb][rb][a[j]]==f[lb][rb][p]&&p>a[j]))
					{
						p=a[j];
					}
				}
			}
		}
		for(int i=1;i<=cnt;i++)
		{
			if(l[i]>=ls&&r[i]<=rs) continue;
			else if(l[i]>=ls)
			{
				for(int j=l[i];j<=rs;j++)
				{
					f[lb][rb][a[j]]--;
				}
				
			}
			else if(r[i]<=rs)
			{
				for(int j=r[i];j>=ls;j--)
				{
					f[lb][rb][a[j]]--;
				}
			}
		}
		cout<<b[p]<<'\n';
		preans=b[p];
	}
	return 0;
}