蒲公英_牛客博客

思路：
注意输入的 $l、r$ 的意思，强制在线处理。
求一个区间的众数不具有区间“区间可加性”，树状数组和线段树去维护非常困难，而分块大段维护、局部朴素就非常的适合。
看完题解自己在实现有点难度，蓝书就点拨一下，不给多余提示。

这题是要用到桶的，所以先把出现的 $a$ 离散化到自然数 $1 \sim mm$ 上。将序列 $n$ 分成 $T$ 段，每段的长度为 $n/T$ ， $T$ 不一定要是 $sqrt(n)$ ，比如这题可以是 $200（200*200=4e4）$ ，每一段的左右端点以及某个下标对应那个段也可以不用数组存，这里我分成了 $sqrt(n)$ 段。选两个段的端点组成新的区间，统计这个区间的众数，同时统计第 $i$ 段数字 $1\sim mm$ 出现次数的前缀和（这里和蓝书描述不太一样，蓝色是说用 $cnt[L][R][mm]$ 存区间每个数出现的次数，数组都开不了这么大，应该只是为了点拨一下，让读者自己思考怎么实现，反复看蓝色的这部分纠结了好久还不懂要干嘛，后面才知道别人都是用前缀和写的）

$l、r$ 对应 $p、q$ 段， $R=ri[p]、L=li[q]$ ，对于 $q-p<=1$ 的情况直接朴素扫描。

显然， $a$ 的序列在区间 $[l,r]$ 中的众数有以下两种情况：
1.区间 $[R+1,L-1]$ 内的众数。
2.出现在区间 $[l,R]$ 或 $[L,r]$ 内的数。
所以如果 $q-p>1$ ，我们只需要枚举区间 $[l,R]$ 或 $[L,r]$ 内的数，把这些数出现的次数加上在区间 $[R+1,L-1]$ 出现的次数，与区间 $[R+1,L-1]$ 内的众数的次数比较，找出区间 $[l,r]$ 中的众数。
复杂度大概 $O(sqrt(n)^3+2*m*sqrt(n))$

二分的思路是先存每个数x出现的下标，然后用二分函数lower_bound()、upper_bound()找出x在[l,r]中出现的次数，优点是简单一点，空间消耗比前缀和的小，但是时间复杂度大了不少。【二分代码】

Code：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=4e4+7,maxm=2e2+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[maxn],aa[maxn],li[maxm],ri[maxm],pos[maxn],more[maxm][maxm],cnt[maxm][maxn],tmp[maxn];
int solve(int l,int r) {
    int p=pos[l],q=pos[r],ans=0,mx=0;
    if(q-p<=1) {
        for(int i=l; i<=r; ++i) {
            tmp[aa[i]]+=1;
            if(tmp[aa[i]]>mx) {
                mx=tmp[aa[i]];
                ans=aa[i];
            } else if(tmp[aa[i]]==mx&&aa[i]<ans) ans=aa[i];
        }
        for(int i=l; i<=r; ++i) tmp[aa[i]]-=1;

    } else {
        ans=more[p+1][q-1],mx=cnt[q-1][ans]-cnt[p][ans];
        for(int i=l; i<=ri[p]; ++i) tmp[aa[i]]+=1;
        for(int i=li[q]; i<=r; ++i) tmp[aa[i]]+=1;

        for(int i=l,x; i<=ri[p]; ++i) {
            if(!tmp[aa[i]]) continue;
            x = cnt[q-1][aa[i]] - cnt[p][aa[i]] + tmp[aa[i]];
            tmp[aa[i]]=0;
            if( x > mx ) {
                mx=x;
                ans=aa[i];
            } else if(x==mx&&aa[i]<ans) ans=aa[i];
        }
        for(int i=li[q],x; i<=r; ++i) {
            if(!tmp[aa[i]]) continue;
            x = cnt[q-1][aa[i]] - cnt[p][aa[i]] + tmp[aa[i]];
            tmp[aa[i]]=0;
            if( x > mx ) {
                mx=x;
                ans=aa[i];
            } else if(x==mx&&aa[i]<ans) ans=aa[i];
        }
    }
    return ans;
}
int main() {
    int n=read(),m=read();
    for(int i=1; i<=n; ++i) aa[i]=a[i]=read();
    int t=sqrt(n);
    for(int i=1; i<=t; ++i) {
        li[i]=ri[i-1]+1;
        ri[i]=i*t;
    }
    if(ri[t] < n) t+=1,li[t]=ri[t-1]+1,ri[t]=n;
    sort(a+1,a+1+n);
    int mm=unique(a+1,a+1+n)-a;
    for(int i=1; i<=n; ++i)
        aa[i]=lower_bound(a+1,a+mm,aa[i])-a;

    for(int i=1; i<=t; ++i)
        for(int j=li[i]; j<=ri[i]; ++j)
            pos[j]=i;

    for(int i=t,mx,last; i; --i) {
        mx=last=0;
        for(int j=i; j; --j) {
            for(int k=li[j]; k<=ri[j]; ++k) {
                cnt[i][aa[k]]+=1;
                if(cnt[i][aa[k]]>mx) {
                    mx=cnt[i][aa[k]];
                    last=aa[k];
                } else if(cnt[i][aa[k]]==mx&&aa[k]<last) last=aa[k];
            }
            more[j][i]=last;
        }
    }

    int x,y,pre=0;
    while(m--) {
        x=(read()+pre-1)%n+1,y=(read()+pre-1)%n+1;
        if(x>y) swap(x,y);
        printf("%d\n",pre=a[solve(x,y)]);
    }
    return 0;
}