mxqz 分块

rt，全 WA

#include <bits/stdc++.h>
using namespace std;
int n,m,a[40005],l,r,b[40005],block,lst,hx[505],t[40005],cnt2,sum[40005],now,bl[40005],pre[250][40005],ans[250][250];
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f*x;
}
inline int getsum(int l,int r,int x){
    int res=0;
    if(bl[l]^bl[r]){
        for(int i=l;i<=bl[l]*block;i++) res+=(a[i]==x);
        res+=pre[bl[r]-1][x]-pre[bl[l]][x];
        for(int i=(bl[r]-1)*block+1;i<=r;i++) res+=(a[i]==x);
    }
    else for(int i=l;i<=r;i++)
        res+=(a[i]==x);
    return res;
}
bitset<40005> vis;
int main(){
    n=read(),m=read(),block=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=b[i]=read(),bl[i]=(i-1)/block+1;
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    for(int i=1;i<=n;i++){
        sum[a[i]]++;
        if(i==min(bl[i]*block,n))
            for(int j=1;j<=cnt;j++)
                pre[bl[i]][j]=sum[j];
    }
    for(int i=1;i<=bl[n];i++){
        memset(sum,0,sizeof(sum)),now=0;
        for(int j=(i-1)*block+1;j<=n;j++){
            sum[a[j]]++;
            if(sum[a[j]]>sum[now]||(sum[a[j]]==sum[now]&&a[j]<now)) now=a[j];
            if(j==min(bl[j]*block,n))
                ans[i][bl[j]]=now;
        }
    }
    while(m--){
        l=read(),r=read(),cnt2=0;
        l=(l+lst-1)%n+1,r=(r+lst-1)%n+1;
        if(l>r) swap(l,r);
        lst=0;
        memset(hx,0,sizeof(hx));
        if(bl[l]^bl[r]){
            for(int i=l;i<=bl[l]*block;i++)
                hx[++cnt2]=a[i],t[a[i]]++;
            for(int i=(bl[r]-1)*block+1;i<=r;i++)
                hx[++cnt2]=a[i],t[a[i]]++;
            for(int i=1;i<=cnt2;i++){
                if(!vis[hx[i]])
                    t[hx[i]]+=pre[bl[r]-1][hx[i]]-pre[bl[l]][hx[i]],vis[hx[i]]=1;
                if(t[hx[i]]>t[lst]||(t[hx[i]]==t[lst]&&hx[i]<lst)) lst=hx[i]; 
            }
            int xjd=getsum(l,r,ans[bl[l]+1][bl[r]-1]);
            if(xjd>t[lst]||(xjd==t[lst]&&ans[bl[l]+1][bl[r]-1]<lst)) lst=ans[bl[l]+1][bl[r]-1]; 
        }
        else{
            for(int i=l;i<=r;i++)
                hx[++cnt2]=a[i],t[a[i]]++;
            for(int i=1;i<=cnt2;i++)
                if(t[hx[i]]>t[lst]||(t[hx[i]]==t[lst]&&hx[i]<lst)) 
                    lst=hx[i]; 
        }
        printf("%d\n",lst);
        for(int i=1;i<=cnt2;i++)
            t[hx[i]]=0;
        vis.reset();
    }
    return 0;
}