这题给我 火卓 了很久的复杂度，人都快麻了。

后来发现：

加上如下

if(fro+1<=to)
        {
                ans=0;
                for(int i=ql;i<=qr;i++)
                {
                        rec[a[i]]++;
                        if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
                }
                if(qr-ql+1>=kinds) for(int i=1;i<=kinds;i++) rec[i]=0,vis[i]=0;
                else for(int i=ql;i<=qr;i++) rec[a[i]]=0;
                return mapping[ans];
        }

就会TLE,注释掉就过了。

太离谱了。

本来是注释着看一看哪里超时了的，没想到就过了。

而且注释掉的话，如果两个端点在同一个块内的话还多记录了东西。

求问:

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int range=40005;
const int tem_ran=205;
bool vis[range];
int n,m,l,r,a[range],mapping[range];
int num,len,ans,kinds,b[tem_ran],e[tem_ran],bel[range],rec[range],sum[range][tem_ran],mode[tem_ran][tem_ran];
struct unit{int val,pos;}tem[range];
inline bool cmp(unit a,unit b){return a.val<b.val;}
inline int get_time(int col,int ql,int qr){return sum[col][qr]-sum[col][ql-1];}
inline void devide()
{
	len=sqrt(n);
	kinds=a[tem[n].pos];
	for(int i=1;i<=n;i++)
	{
		int id=(i+len-1)/len;
		bel[i]=id;
		if(!b[id]) b[id]=i;
		if(i%len==0 || i==n) e[id]=i;
		sum[a[i]][id]++;
	}
	num=bel[n];
	for(int i=1;i<=num;i++)
	{
		for(int j=1;j<=kinds;j++) sum[j][i]+=sum[j][i-1];
		for(int j=i;j>=1;j--)
		{
			if(j!=i) mode[j][i]=mode[j][i-1];
			for(int k=b[i];k<=e[i];k++) if(get_time(a[k],j,i)>get_time(mode[j][i],j,i) || (get_time(a[k],j,i)==get_time(mode[j][i],j,i) && a[k]<mode[j][i])) mode[j][i]=a[k];
		}
	}
}
inline int get_mode(int ql,int qr)
{
	int ans,fro=bel[ql],to=bel[qr];
    /*
	if(fro+1<=to)
	{
		ans=0;
		for(int i=ql;i<=qr;i++)
		{
			rec[a[i]]++;
			if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
		}
		if(qr-ql+1>=kinds) for(int i=1;i<=kinds;i++) rec[i]=0,vis[i]=0;
		else for(int i=ql;i<=qr;i++) rec[a[i]]=0;
		return mapping[ans];
	}
    *//此处为被注释（和谐）掉的内容。
	ans=mode[fro+1][to-1];
	vis[ans]=1;
	rec[ans]+=get_time(ans,fro+1,to-1);
	//cout << ans << endl;
	for(int i=b[to];i<=qr;i++)
	{
		rec[a[i]]++;
		if(!vis[a[i]]) rec[a[i]]+=get_time(a[i],fro+1,to-1),vis[a[i]]=1;
		if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
	}
	//cout << ql << " " << e[fro] << "|" << b[to] << " " << qr << endl;;
	for(int i=ql;i<=e[fro];i++)
	{
		rec[a[i]]++;
		if(!vis[a[i]]) rec[a[i]]+=get_time(a[i],fro+1,to-1),vis[a[i]]=1;
		if(rec[a[i]]>rec[ans] || (rec[a[i]]==rec[ans] && a[i]<ans)) ans=a[i];
	}
	if(qr-b[to]+1+e[fro]-ql+1>=kinds) for(int i=1;i<=kinds;i++) rec[i]=0,vis[i]=0;
	else
	{
		rec[mode[fro+1][to-1]]=vis[mode[fro+1][to-1]]=0;
		for(int i=b[to];i<=qr;i++) rec[a[i]]=vis[a[i]]=0;
		//cout << ql << " " << e[fro] << "|" << b[to] << " " << qr << endl;;
		for(int i=ql;i<=e[fro];i++) rec[a[i]]=vis[a[i]]=0;
	}
	return mapping[ans];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&tem[i].val),tem[i].pos=i;
	sort(tem+1,tem+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		a[tem[i].pos]=a[tem[i-1].pos];
		if(i==1 || tem[i-1].val!=tem[i].val) a[tem[i].pos]++;
		mapping[a[tem[i].pos]]=tem[i].val;
	}
	devide();
	while(m--)
	{
		scanf("%d%d",&l,&r);
		l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;
		if(r<l) swap(l,r);
		ans=get_mode(l,r);
		printf("%d\n",ans);
	}
	return 0;
}