记录编号	587579	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	蒲公英	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.255 s
提交时间	2024-04-10 19:50:20	内存使用	140.22 MiB

#include <bits/stdc++.h>
using namespace std;
//分块 
#define ll long long
const int N = 4e5+10,M = 210;
const ll inf = 1e17;
int n,m;
short cnt[N][M];
int s[M][M],a[N],c[N],b[N];
int L[N],R[N],bl[N],B,t,las;

void prework(){
    B = sqrt(n),t = (n-1)/B+1;
    for(int i = 1;i <= t;i++)L[i] = (i-1)*B+1,R[i] = min(i*B,n);
    for(int i = 1;i <= n;i++)bl[i] = (i-1)/B+1;
    
    for(int i = 1;i <= t;i++){
        for(int j = i;j <= t;j++){
            s[i][j] = s[i][j-1];
            for(int k = L[j];k <= R[j];k++){
                c[a[k]]++;
                if(c[a[k]] == c[s[i][j]] && a[k] < s[i][j])s[i][j] = a[k];
                else if(c[a[k]] > c[s[i][j]])s[i][j] = a[k];
            }
        }
        for(int j = L[i];j <= n;j++)c[a[j]]--;
    }//s数组 
    
    for(int i = 1;i <= t;i++){
        for(int j = 1;j <= n;j++)cnt[j][i] += cnt[j][i-1];
        for(int j = L[i];j <= R[i];j++)cnt[a[j]][i]++;
    }//cnt数组 
}

int ask(int l,int r){
    int p = bl[l],q = bl[r];
    if(p == q){
        int ans = 0;
        for(int i = l;i <= r;i++){
            c[a[i]]++;
            if(c[a[i]] == c[ans] && a[i] < ans)ans = a[i];
            else if(c[a[i]] > c[ans])ans = a[i];
        }
        for(int i = l;i <= r;i++)c[a[i]]--;
        return ans;
    }
    int ans = s[p+1][q-1];
    for(int i = l;i <= R[p];i++){
        c[a[i]]++;
        if(c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p] == c[ans]+cnt[ans][q-1]-cnt[ans][p] && a[i] < ans)ans = a[i];
        else if(c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p] > c[ans]+cnt[ans][q-1]-cnt[ans][p])ans = a[i];
    }
    for(int i = L[q];i <= r;i++){
        c[a[i]]++;
        if(c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p] == c[ans]+cnt[ans][q-1]-cnt[ans][p] && a[i] < ans)ans = a[i];
        else if(c[a[i]]+cnt[a[i]][q-1]-cnt[a[i]][p] > c[ans]+cnt[ans][q-1]-cnt[ans][p])ans = a[i];
    }
    for(int i = l;i <= R[p];i++)c[a[i]]--;
    for(int i = L[q];i <= r;i++)c[a[i]]--;
    return ans;
}
int main(){
	freopen("Dandelion.in","r",stdin);
    freopen("Dandelion.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]),b[i] = a[i];
    sort(b+1,b+1+n);
    int l = unique(b+1,b+1+n) - (b+1);
    for(int i = 1;i <= n;i++)a[i] = lower_bound(b+1,b+1+l,a[i]) - b;
    prework();
    
    for(int i = 1;i <= m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l = (l+las-1)%n+1,r = (r+las-1)%n+1;
        if(l > r)swap(l,r);
        printf("%d\n",las=b[ask(l,r)]);
    }

	return 0;

}