参考代码链接

#pragma GCC optimize(2)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int N = 1e5 + 10, B = 1e3 + 10;

int n, m, block;
int a[N], b[N], f[N], tot;
int d[B][B];
int ct[N];
vector<int> g[N];

void build(){
    block = max(1, (int)(n / sqrt(m * log2(n))));
    // 块 从一开始计数
    for(int i = 1;i <= n;i ++ ){
        b[i] = (i - 1) / block + 1;
        // cout << b[i] << endl;
    }
}

void solve(int x){
    memset(ct, 0, sizeof ct);
    int mx = -1, ans = 0;
    for(int i = (x - 1) * block + 1;i <= n;i ++ ){
        ct[a[i]] ++ ;
        if(mx < ct[a[i]] || (mx == ct[a[i]] && ans > a[i])){
            mx = ct[a[i]];
            ans = a[i];
        }
        d[x][b[i]] = ans;
    }
}
int count(int l,int r,int val){
    return upper_bound(g[val].begin(), g[val].end(), r) - lower_bound(g[val].begin(), g[val].end(), l);
}
int query(int l,int r){
    if(b[l] == b[r]){
        int mx = 0, res;
        for(int i = l;i <= r;i ++ ){
            int t = count(l, r, a[i]);
            if(mx < t) mx = t, res = a[i];
            else if(mx == t && a[i] < res) res = a[i];
        }
        return res;
    }

    int ans = d[b[l] + 1][b[r] - 1];
    int mx = count(l, r, ans);
    for(int i = l;i <= b[l] * block;i ++ ){
        int t = count(l, r, a[i]);
        if(t > mx) mx = t, ans = a[i];
        else if(t == mx && ans > a[i]) ans = a[i];
    }

    for(int i = (b[r] - 1) * block + 1;i <= r;i ++ ){
        int t = count(l, r, a[i]);
        if(t > mx) mx = t, ans = a[i];
        else if(t == mx && ans > a[i]) ans = a[i];
    }

    return ans;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++ ){
        scanf("%d", &a[i]);
        f[i] = a[i];
    }

    build();
    sort(f + 1, f + 1 + n);
    int N = unique(f + 1, f + 1 + n) - f - 1;

    for(int i = 1;i <= n;i ++ ){
        a[i] = lower_bound(f + 1, f + 1 + N, a[i]) - f;
        g[a[i]].push_back(i);
    }
    int ans = 0;
    for(int i = 1;i <= b[n];i ++ ){
        solve(i);
    }

    while(m -- ){
        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);
        ans = f[query(l, r)];
        printf("%d\n", ans);
    }

    return 0;
}