区间众数预处理求调

初步诊断为预处理 的问题：

#include <bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
    char buf[1 << 23], * p1 = buf, * p2 = buf, obuf[1 << 23], * O = obuf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
    return x * f;
}
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pi;
const int N = 1e5 + 10;
int n, c, m;
int a[N];
const int SIZ = 20;
int bel[N], l[SIZ + 10], r[SIZ + 10];
int lst[N];
int ls[N];
int cnt[N][SIZ + 10], maj[SIZ + 10][SIZ + 10];
int getcnt (int l, int r, int val) {
    return cnt[val][r] - cnt[val][l - 1] + ls[val];
}
void init () {
    for (int i = 1; i <= n; i ++) {
        bel[i] = (i - 1) / SIZ + 1;
        if (bel[i] != bel[i - 1]) l[bel[i]] = i, r[bel[i] - 1] = i - 1;
    }
    r[bel[n]] = n;
    for (int i = 1; i <= n; i ++) {
        cnt[a[i]][bel[i]] ++;
        if (bel[lst[a[i]]] != bel[i]) cnt[a[i]][bel[i]] += cnt[a[i]][bel[lst[a[i]]]];
        lst[a[i]] = i;
        for (int j = 1; j <= bel[i]; j ++) {
            if (i == l[bel[i]]) maj[j][bel[i]] = maj[j][bel[i] - 1];
            int tmp = getcnt(j, bel[i], a[i]);
            int tmp2 = getcnt(j, bel[i], maj[j][bel[i]]);
            if (tmp > tmp2) maj[j][bel[i]] = a[i];
            else if (tmp == tmp2) maj[j][bel[i]] = min(maj[j][bel[i]], a[i]);
        }
        if (i == r[bel[i]]) {
            for (int num = 1; num <= c; num ++) {
                if (!cnt[num][bel[i]]) cnt[num][bel[i]] = cnt[num][bel[i] - 1];
            }
        }
    }
}
vector<int> lsh;
int query (int ql, int qr) {
    int bl = bel[ql], br = bel[qr];
    int res = 0;
    vector<int> opt;
    if (br - bl + 1 <= 2) {
//      cout << bl << ' ' << br << endl;
        for (int i = ql; i <= qr; i ++)
            ls[a[i]] ++;
        for (int i = ql; i <= qr; i ++) {
//          cout << a[i] << ' ';
            if (ls[a[i]] > ls[res]) res = a[i];
            else if (ls[a[i]] == ls[res]) res = min(res, a[i]);
        }
//      cout << endl;
        for (int i = ql; i <= qr; i ++) ls[a[i]] --;
        return lsh[res - 1];
    }
    res = maj[bl + 1][br - 1];
    cout << lsh[res - 1] << endl;
    cout << getcnt(bl + 1, br - 1, res) << endl;
    // cout << getcnt(bl + 1, br - 1, lower_bound(lsh.begin(), lsh.end(), 39881273) - lsh.begin() + 1) << endl;
    for (int i = ql; i <= r[bl]; i ++) {
        ls[a[i]] ++;
        if (ls[a[i]] == 1) opt.push_back(a[i]);
    }
    for (int i = l[br]; i <= qr; i ++) {
        ls[a[i]] ++;
        if (ls[a[i]] == 1) opt.push_back(a[i]);
    }
    for (auto x : opt) {
        cout << lsh[x - 1] << ' ' << getcnt(bl + 1, br - 1, x) << endl;
        int tmp = getcnt(bl + 1, br - 1, x);
        if (tmp > getcnt(bl + 1, br - 1, res)) res = x;
        else if (tmp == getcnt(bl + 1, br - 1, res)) res = min(res, x);
    }
    cout << getcnt(bl + 1, br - 1, res) << endl;
    for (int i = ql; i <= r[bl]; i ++)
        ls[a[i]] --;
    for (int i = l[br]; i <= qr; i ++)
        ls[a[i]] --;
    return lsh[res - 1];
}

signed main() {
    freopen("P4168_1.in", "r", stdin);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) a[i] = read(), lsh.push_back(a[i]);
    sort (lsh.begin(), lsh.end());
    lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    for (int i = 1; i <= n; i ++) a[i] = lower_bound(lsh.begin(), lsh.end(), a[i]) - lsh.begin() + 1;
    c = lsh.size();
    init();
    int ans = 0;
    while (m --) {
        int l, r;
        l = read(), r = read();
        l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
        if (l > r) swap(l, r);
        cout << l << ' ' << r << endl;
        ans = query(l, r);
        cout <<"----" << ans << endl;
    }
    return 0;
}