[Violet]蒲公英

分块题。

巨神Monster_Qi讲了以后发现这道题并不难，在此Orz

预处理两个数组，sum和ans。

离散化以后找前i块j出现了几次，和i到j块的众数是多少。这样的复杂度是n√n的，然后查询的时候边角块一个一个往进加，看能不能更新众数即可。

（不是我故意压行，是这个条件太多了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int blo=200;
int n,a[40005],sum[205][40005],ans[205][205],bl[40005],b[40005],m,l,r,tp[40005];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1,scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);int u=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+u,a[i])-b;
    for(int i=1;i<=n;i++) {
        sum[bl[i]][a[i]]++;
    }
    for(int i=1;i<=(n-1)/blo+1;i++) {
        for(int j=1;j<=u;j++) {
            sum[i][j]+=sum[i-1][j];
        }
    }
    for(int j=1;j<=(n-1)/blo+1;j++) {
        for(int i=j;i<=(n-1)/blo+1;i++) {
            ans[i][j]=ans[i-1][j];
            for(int k=blo*(j-1)+1;k<=blo*i;k++) {
                if(
                sum[i][a[k]]-sum[j-1][a[k]]>sum[i][ans[i][j]]-sum[j-1][ans[i][j]]
                ||(sum[i][a[k]]-sum[j-1][a[k]]==sum[i][ans[i][j]]-sum[j-1][ans[i][j]]&&a[k]<ans[i][j])
                ) ans[i][j]=a[k];
            }
        }
    }
    int l,r,res=0;
    while(m--) {
        scanf("%d%d",&l,&r);
        l=(l+res-1)%n+1,r=(r+res-1)%n+1;res=0;
        if(l>r) swap(l,r);
        int blol,blor;
        if(bl[l]==bl[r]) {
            for(int i=l;i<=r;i++) {
                tp[a[i]]++;
                if(tp[a[i]]>tp[res]||(tp[a[i]]==tp[res]&&a[i]<res)) res=a[i];
            }
            for(int i=l;i<=r;i++) tp[a[i]]--;
            res=b[res];
            printf("%d
",res);
            continue;
        }
        if((l-1)%blo==0) blol=bl[l];else blol=bl[l]+1;
        if(r%blo==0) blor=bl[r];else blor=bl[r]-1;
        res=ans[blor][blol];
        for(int i=l;bl[i]!=blol;i++) {
            tp[a[i]]++;
            if(tp[a[i]]+sum[blor][a[i]]-sum[blol-1][a[i]]>tp[res]+sum[blor][res]-sum[blol-1][res]
            ||(tp[a[i]]+sum[blor][a[i]]-sum[blol-1][a[i]]==tp[res]+sum[blor][res]-sum[blol-1][res]&&a[i]<res)
            ) res=a[i];
        }
        for(int i=r;bl[i]!=blor;i--) {
            tp[a[i]]++;
            if(tp[a[i]]+sum[blor][a[i]]-sum[blol-1][a[i]]>tp[res]+sum[blor][res]-sum[blol-1][res]
            ||(tp[a[i]]+sum[blor][a[i]]-sum[blol-1][a[i]]==tp[res]+sum[blor][res]-sum[blol-1][res]&&a[i]<res)
            )res=a[i];
        }
        for(int i=l;bl[i]!=blol;i++) {
            tp[a[i]]--;
        }
        for(int i=blor*blo+1;i<=r;i++) {
            tp[a[i]]--;
        }
        res=b[res];
        printf("%d
",res);
    }
    
}