C++14(g++5.4) 解法, 执行用时: 607ms, 内存消耗: 4840K, 提交时间: 2020-03-11 16:03:04

# include <bits/stdc++.h>
using namespace std;
const int SIZE=40005;
int n,m,tot=0,x,y,ans=0;
int a[SIZE],b[SIZE],cnt[SIZE],val[SIZE];
int f[1005][1005];
map<int,int>mp;
vector<int>G[SIZE];
int check(int l,int r,int x){
    return upper_bound(G[x].begin(),G[x].end(),r)-lower_bound(G[x].begin(),G[x].end(),l);
}
int query(int x,int y){
    int ret=f[b[x]+1][b[y]-1],Max=check(x,y,ret);
    for(int i=x;i<=min(b[x]*100,y);i++){
        int t=check(x,y,a[i]);
        if(t>Max || (t==Max && val[a[i]]<val[ret]))ret=a[i],Max=t;
    }
    if(b[x]!=b[y]){
        for(int i=(b[y]-1)*100+1;i<=y;i++){
            int t=check(x,y,a[i]);
            if(t>Max || (t==Max && val[a[i]]<val[ret]))ret=a[i],Max=t;
        }
    }
    return ret;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!mp[a[i]])mp[a[i]]=++tot,val[tot]=a[i];
        a[i]=mp[a[i]];
        G[a[i]].push_back(i);
    }
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)b[i]=(i-1)/100+1;
    for(int i=1;i<=b[n];i++){
        memset(cnt,0,sizeof(cnt));
        int Max=0,ret=0;
        for(int j=(i-1)*100+1;j<=n;j++){
            cnt[a[j]]++;
            if(cnt[a[j]]>Max || (cnt[a[j]]==Max && val[a[j]]<val[ret]))ret=a[j],Max=cnt[a[j]];
            f[i][b[j]]=ret;
        }
    }
    while(m--){
        scanf("%d %d",&x,&y);
        x=(x+ans-1)%n+1,y=(y+ans-1)%n+1;
        if(x>y)swap(x,y);
        ans=val[query(x,y)];
        printf("%d\n",ans);
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 268ms, 内存消耗: 6904K, 提交时间: 2020-11-05 16:31:53

#include<bits/stdc++.h>
#define blo(i) (i-1)/len+1
#define cnt(i) upper_bound(p[i].begin(),p[i].end(),r)-lower_bound(p[i].begin(),p[i].end(),l)
using namespace std;
const int nn=41105,TT=1105;
int n,m,len,tt,a[nn],b[nn],c[nn];
int maxi,l,r,x,y,L[TT],R[TT],f[TT][TT];
int*ed;
vector<int>p[nn];
void up(int x){
	int ct=cnt(x);
	if(ct>maxi||(ct==maxi&&x<c[0]))
		c[0]=x,maxi=ct;
}int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i),b[i]=a[i];
	sort(b+1,b+n+1),ed=unique(b+1,b+n+1);
	len=sqrt(log(n)/log(2)*n),len=len?n/len:n;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,ed,a[i])-b,
		p[a[i]].emplace_back(i);
	for(;(r=R[tt++])<n;){
		L[tt]=r+1,R[tt]=min(n,r+len);
		memset(c,0,sizeof c);
		for(int i=tt;i;i--){
			f[i][tt]=f[i+1][tt];
			for(int j=L[i];j<=R[i];j++){c[a[j]]++;
				if((c[a[j]]==c[f[i][tt]]&&a[j]<f[i][tt])
				||c[a[j]]>c[f[i][tt]])f[i][tt]=a[j];
			}
		}
	}while(m--){
		scanf("%d%d",&l,&r);
		l=(l+b[c[0]]-1)%n+1,r=(r+b[c[0]]-1)%n+1;
		c[0]=maxi=0;
		if(l>r)swap(l,r);
		if((x=blo(l))==(y=blo(r)))
			for(int i=l;i<=r;i++)up(a[i]);
		else{c[0]=f[x+1][y-1],maxi=cnt(c[0]);
			for(int i=l;i<=R[x];i++)up(a[i]);
			for(int i=L[y];i<=r;i++)up(a[i]);
		}printf("%d\n",b[c[0]]);
	}return 0;
}