分块过#17，18，10pts

提交链接

#include<bits/stdc++.h>
#define na putchar('\n')
using namespace std;
inline int read();
inline void write(long long n);
const int MAXN=4e4+5;
int n,m,k,a[MAXN],b[MAXN],cnt[MAXN][222],cobe[MAXN],last,x,aft[MAXN][222],i1;
vector<int>q;
vector<int>g;
int slove_easy(int l,int r){
    int ans,maxn=0;
    q.clear(),g.clear();
    q.resize(k+1);
    for(int i=l;i<=r;i++){
        q[a[i]]++;
        if(q[a[i]]==1)g.push_back(a[i]);
    }
    for(int i=0;i<(int)g.size();i++){
        if(q[g[i]]>maxn){
            maxn=q[g[i]];
            ans=g[i];
        }else if(q[g[i]]==maxn&&g[i]<ans){
            ans=g[i];
        }
    }
    return ans;
}
int slove_hard(int l,int r,int lk,int rk){
    int ans,maxn=0;
    q.clear(),g.clear();
    q.resize(k+1);
    for(int i=l;i<=min(n,lk*i1);i++){
        q[a[i]]++;
        if(q[a[i]]==1)g.push_back(a[i]);
    }
    for(int i=(rk-1)*i1+1;i<=r;i++){
        q[a[i]]++;
        if(q[a[i]]==1)g.push_back(a[i]);
    }
    for(int i=0;i<(int)g.size();i++){
        int s=g[i];
        int sum=q[s]+aft[s][rk-1]-aft[s][lk];
        if(sum>maxn){
            ans=s;
            maxn=sum;
        }else if(sum==maxn&&s<ans){
            ans=s;
        }
    }
    for(int i=lk+1;i<=rk-1;i++){
        int s=cobe[i];
        int sum=q[s]+aft[s][rk-1]-aft[s][lk];
        if(sum>maxn){
            ans=s;
            maxn=sum;
        }else if(sum==maxn&&s<ans){
            ans=s;
        }
    }
    return ans;
}
int main(){
//  freopen("P4168_1.in","r",stdin);
//  freopen("P4168_hack.txt","w",stdout);
    n=read(),m=read();
//  m=1;
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    k=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+k+1,a[i])-b;
    }
    /*
    printf("check 1:\n");
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    na;
    */
    i1=sqrt(n);
    q.resize(k+1);
    for(int i=1;i<=n;i++){
        int s=a[i];
        q[s]++;
        if(i%i1==0){
            int maxn=0;
            for(int j=1;j<=k;j++){
                if(q[j]>maxn){
                    cobe[i/i1]=j;
                    maxn=q[j];
                }
            }
            for(int j=1;j<=k;j++){
                cnt[j][i/i1]=q[j];
            }
            q.clear();
            q.resize(k+1);
        }
    }
    last=n/i1;
    if(n%i1!=0){
        last++;
        int maxn=0;
        for(int j=1;j<=k;j++){
            cobe[n/i1+1]=j;
            maxn=q[j];
        }
        for(int j=1;j<=k;j++){
            cnt[j][n/i1+1]=q[j];
        }
    }
    q.clear();
    /* 
    printf("check 2:\n");
    for(int i=1;i<=last;i++){
        for(int j=1;j<=k;j++){
            printf("%d ",cnt[j][i]);
        }
        printf("\n");
    }
    */
    /*
    printf("check 3:\n");
    for(int i=1;i<=last;i++){
        printf("i=%d ans=%d",i,cobe[i]);
        printf("\n");
    }
    */
    for(int i=1;i<=k;i++){
        for(int j=1;j<=last;j++){
            aft[i][j]=aft[i][j-1]+cnt[i][j];
        }
    }
    while(m--){
        int l,r;
        l=read(),r=read();
//      l=282,r=428;
        l=((l+x-1)%n)+1,r=((r+x-1)%n)+1;
        if(l>r)swap(l,r);
        int ls=(l-1)/i1+1,rs=(r-1)/i1+1;
        printf("check 4: true input:\nl=%d r=%d\nblock into:\nlk=%d rk=%d\n",l,r,ls,rs);
        if(rs-ls<2){
            x=slove_easy(l,r);
        }else{
            x=slove_hard(l,r,ls,rs);
        }
        x=b[x];
        write(x);
        na;
//      na;
    }
    return 0;
}
/*
  cobe->块内众数编号
  cnt->块中数字出现数
  aft->cnt前缀和
  slove_easy->无完整块解法
  slove_hard->有完整块解法
*/
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(long long n){
    if(n<0){putchar('-');n=-n;}
    if(n>9){write(n/10);}
    putchar(n%10+'0');
}