分块WA0求调

rt

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=2e2+10;
int n,m;
int a[N],b[N];
int bel[N],lx[N],rx[N],cnt,B;
int sum;
int s[M][N],p[M][M];
int t[N];
signed main()
{
    cin>>n>>m;B=sqrt(n);
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    sum=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+sum+1,a[i])-b;
    for(int i=1,j;i<=n;i=j+1)
    {
        j=min(n,i+B-1);
        lx[++cnt]=i;rx[cnt]=j;
        for(int ii=i;ii<=j;ii++)
            bel[ii]=cnt;
    }
    for(int i=1;i<=n;i++)
        s[bel[i]][a[i]]++;
    for(int i=1;i<=cnt;i++)
        for(int j=0;j<=sum;j++)
            s[i][j]+=s[i-1][j];
    for(int i=1;i<=cnt;i++)
        for(int j=i;j<=cnt;j++)
        {
            int ans=p[i][j-1];
            for(int k=lx[j];k<=rx[j];k++)
                if((s[j][a[k]]-s[i-1][a[k]]>s[j][ans]-s[i-1][ans])||(s[j][a[k]]-s[i-1][a[k]]==s[j][ans]-s[i-1][ans]&&a[k]<ans))
                    ans=a[k];
            p[i][j]=ans;
        }
    int res=0;
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        l=(l+res-1)%n+1;
        r=(r+res-1)%n+1;
        if(l>r)swap(l,r);
        int mx=0;
        if(bel[r]-bel[l]<=1)
        {

            for(int i=l;i<=r;i++)
                t[a[i]]++;
            for(int i=l;i<=r;i++)   
                if(t[a[i]]>t[mx]||(t[a[i]]==mx&&a[i]<mx))
                    mx=a[i];
            for(int i=l;i<=r;i++)
                t[a[i]]=0;
        }
        else
        {
            mx=p[bel[l]+1][bel[r]-1];
            for(int i=l;i<=rx[bel[l]];i++)t[a[i]]++;
            for(int i=lx[bel[r]];i<=r;i++)t[a[i]]++;
            for(int i=l;i<=rx[bel[l]];i++)
            {
                int ans=t[mx]+s[bel[r]-1][mx]-s[bel[l]][mx];
                int now=t[a[i]]+s[bel[r]-1][a[i]]-s[bel[l]][a[i]];
                if(now>ans||(now==ans&&a[i]<mx))
                    mx=a[i];
            }
            for(int i=lx[bel[r]];i<=r;i++)
            {
                int ans=t[mx]+s[bel[r]-1][mx]-s[bel[l]][mx];
                int now=t[a[i]]+s[bel[r]-1][a[i]]-s[bel[l]][a[i]];
                if(now>ans||(now==ans&&a[i]<mx))
                    mx=a[i];
            }
            for(int i=l;i<=rx[bel[l]];i++)t[a[i]]=0;
            for(int i=lx[bel[r]];i<=r;i++)t[a[i]]=0;
        }
        res=b[mx];
        cout<<res<<endl;
    }
    return 0;
}