wy's Blog

2724: [Violet 6]蒲公英

Description

Input

Output

Sample Input

Sample Output

HINT

分块算法

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,M,K,P,o;
int ans;
struct point{
    int x,k,s;
}A[40010];
int cnt[210][40010];
int Ans[210][210];
int vtimes[40010];
int ctmp[40010];
int Q[40010];
int cmp_x(const point &a,const point &b){
    return a.x<b.x;
}
int cmp_k(const point &a,const point &b){
    return a.k<b.k;
}
void Discretization(){
    sort(A+1,A+N+1,cmp_x);
    for (int i=1;i<=N;++i){
        if (i==1||A[i].x!=A[i-1].x){
            A[i].s=++P;         
            Q[P]=A[i].x; 
        }
        else A[i].s=P;
    }
    sort(A+1,A+N+1,cmp_k);
}
void PreTreatment(){
    int w=N/K;
    if (N%K) ++w;
    o=0;
    for (int i=1;i<=N;++i){
        if (i%K==1) ++o;
        for (int j=o;j<=w;++j)
            ++cnt[j][A[i].s];
    }   
    int Mod=0;
    for (int k=1;k<=o;++k){
        memset(vtimes+1,0,sizeof(int)*P);
        for (int i=(k-1)*K+1;i<=N;++i){
            vtimes[A[i].s]++;
            if (vtimes[A[i].s]>vtimes[Mod]||(vtimes[A[i].s]==vtimes[Mod]&&Mod>A[i].s))
                Mod=A[i].s;
            if (!(i%K))
                Ans[k][i/K]=Mod;
        }       
    }   
}
int main(){
    scanf("%d%d",&N,&M);
    K=sqrt(N);
    for (int i=1;i<=N;++i){
        scanf("%d",&A[i].x);
        A[i].k=i;   
    }
    Discretization();
    PreTreatment();
    for (;M--;){
        memset(ctmp+1,0,sizeof(int)*P);
        int l,r;
        scanf("%d%d",&l,&r);
        l=(l+ans-1)%N+1;
        r=(r+ans-1)%N+1;
        if (l>r) swap(l,r);
        int x=(l-1)/K+1;
        int y=(r-1)/K+1;
        if (l%K!=1) ++x;
        if (r%K) --y;
        int Mod;
        if (x>y){
            Mod=0;
            int times=0;
            for (int i=l;i<=r;++i){
                ++ctmp[A[i].s];
                if (ctmp[A[i].s]>times||(ctmp[A[i].s]==times&&Mod>A[i].s)){
                    Mod=A[i].s;
                    times=ctmp[A[i].s];
                }
            }
        }
        else{
            Mod=Ans[x][y];
            int times=cnt[y][Mod]-cnt[x-1][Mod];
            for (int i=l;i<=(x-1)*K;++i){
                ++ctmp[A[i].s];
                int tmp=cnt[y][A[i].s]-cnt[x-1][A[i].s]+ctmp[A[i].s];
                if (tmp>times||(tmp==times&&Mod>A[i].s)){
                    Mod=A[i].s;
                    times=tmp;
                }
            }
            for (int i=y*K+1;i<=r;++i){
                ++ctmp[A[i].s];
                int tmp=cnt[y][A[i].s]-cnt[x-1][A[i].s]+ctmp[A[i].s];
                if (tmp>times||(tmp==times&&Mod>A[i].s)){
                    Mod=A[i].s;
                    times=tmp;
                }
            }           
        }
        ans=Q[Mod];
        printf("%d\n",Q[Mod]);
    }
}