p4168 [Violet]蒲公英（分块）

区间众数的重题

和数列分块入门9双倍经验还是挺好的

然后开O2水过

好像有不带log的写法啊

之后在补就是咕咕咕

// luogu-judger-enable-o2

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <cmath>

using namespace std;

int m,belong[100100],f[1000][1000],sz,blocknum,n,val[100100],id=0,cnt[100100],a[100100],ans=0;

vector<int> Vec[100100];

map<int,int> To;

void calbe(int n){

    for(int i=1;i<=n;i++)

        belong[i]=(i-1)/sz+1;

}

void pre(int x){

    memset(cnt,0,sizeof(cnt));

    int ans=0,ansto=0;

    for(int i=(x-1)*sz+1;i<=n;i++){

        cnt[a[i]]++;

        if(cnt[a[i]]>ansto||(val[a[i]]<=val[ans]&&cnt[a[i]]>=ansto))

            ans=a[i],ansto=cnt[a[i]];

        f[x][belong[i]]=ans;

    }

}

int query(int l,int r,int c){

    return upper_bound(Vec[c].begin(),Vec[c].end(),r)-lower_bound(Vec[c].begin(),Vec[c].end(),l);

}

int query(int l,int r){

    int lsx=belong[l];

    int rex=belong[r];

    int ans=0,ansto=0,mid;

    for(int i=l;i<=min(lsx*sz,r);i++)

        if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto))

            ans=a[i],ansto=mid;

    if(lsx!=rex){

        for(int i=(rex-1)*sz+1;i<=r;i++)

            if((mid=query(l,r,a[i]))>ansto||(val[a[i]]<=val[ans]&&mid>=ansto))

                ans=a[i],ansto=mid;

        if(lsx+1<=rex-1)

            if((mid=query(l,r,f[lsx+1][rex-1]))>ansto||(val[f[lsx+1][rex-1]]<=val[ans]&&mid>=ansto))

                ans=f[lsx+1][rex-1],ansto=mid;

    }

    return ans;

}

int main(){

    // freopen("1.in","r",stdin);

    // freopen("test.out","w",stdout);

    scanf("%d %d",&n,&m);

    sz=150;

    blocknum=n/sz;

    if(n%sz)

        blocknum++;

    calbe(n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        if(!To[a[i]]){

            To[a[i]]=++id;

            val[id]=a[i];

        }

        a[i]=To[a[i]];

        Vec[a[i]].push_back(i);

    }

    for(int i=1;i<=blocknum;i++)

        pre(i);

    for(int i=1;i<=m;i++){

        int l,r;

        scanf("%d %d",&l,&r);

        l=(l+ans-1)%n+1;

        r=(r+ans-1)%n+1;

        if(r<l)

            swap(l,r);

        printf("%d\n",ans=val[query(l,r)]);

    }

    return 0;

}