区间众数

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[100005], st[100005], ed[100005];
struct MO {
    int L, R, idx;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        return x.R < y.R;
    }
};
int a[100005];
int tcnt[100005], cnt[100005];
int sum = 0;
void add(int idx) {
    cnt[a[idx]]++;
    sum = max(sum, cnt[a[idx]]);
}
void del(int idx) {
    cnt[a[idx]]--;
}
int main() {
    int n, m;
    cin >> n >> m;
    {
        int B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    vector<int> idx(1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    vector<MO> mo;
    for (int i = 0 ; i < m ; i++) {
        int L, R;
        cin >> L >> R;
        mo.push_back({L, R, i});
    }
    sort(begin(mo), end(mo));
    vector<int> ans(mo.size());
    int lst = belong[mo[0].L], R = ed[lst], L = R + 1;
    for (auto &[QL, QR, idx] : mo) {
        if (belong[QL] == belong[QR]) { // 在一个块内, 暴力查询
            int temp = 0;
            for (int j = QL ; j <= QR ; j++) {
                tcnt[a[j]]++;
                temp = max(temp, tcnt[a[j]]);
            }
            for (int j = QL ; j <= QR ; j++) {
                tcnt[a[j]]--;
            }
            ans[idx] = temp;
            continue;
        }
        if (lst != belong[QL]) {
            // 如果当前不在查询块内, 则将 L 和 R 移至块内
            while (R > ed[belong[QL]]) {
                del(R--);
            }
            while (L < ed[belong[QL]] + 1) {
                del(L++);
            }
            sum = 0;
            lst = belong[QL];
        }
        while (R < QR) { // 向右扩, 直至 R = QR
            add(++R);
        }
        int temp = sum, L1 = L;
        while (L1 > QL) { // 新开向左扩, 直至 L1 = QL
            add(--L1);
        }
        ans[idx] = sum;
        while (L1 < L) { // 回滚左端点
            del(L1++);
        }
        sum = temp;
    }
    for (int i = 0 ; i < m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[40005], st[40005], ed[40005];
int a[40005];
int cnt[40][40][40005], mode[40][40], tcnt[40005];
vector<int> ind(1);
void add(int L, int R, int idx) {
    cnt[L][R][a[idx]]++;
    if (cnt[L][R][a[idx]] > cnt[L][R][0] || (cnt[L][R][a[idx]] == cnt[L][R][0] && ind[a[idx]] < mode[L][R])) {
        mode[L][R] = ind[a[idx]];
        cnt[L][R][0] = cnt[L][R][a[idx]];
    }
}
void del(int L, int R, int idx) {
    cnt[L][R][a[idx]]--;
}
int main() {
    int n, m;
    cin >> n >> m;
    int B = pow(n, 0.3333333333);
    {
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        ind.push_back(a[i]);
    }
    sort(begin(ind), end(ind));
    ind.resize(unique(begin(ind), end(ind)) - begin(ind));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(ind), end(ind), a[i]) - begin(ind);
    }
    for (int i = 1 ; i <= B ; i++) {
        for (int j = i ; j <= B ; j++) {
            for (int k = st[i] ; k <= ed[j] ; k++) {
                add(i, j, k);
            }
        }
    }
    int ans = 0;
    for (int i = 1 ; i <= m ; i++) {
        int L, R;
        cin >> L >> R;
        L = (L + ans - 1) % n + 1;
        R = (R + ans - 1) % n + 1;
        if (L > R) {
            swap(L, R);
        }
        int x = belong[L], y = belong[R];
        if (abs(x - y) <= 2) { // 如果查询在一个块内, 暴力查询
            ans = 0;
            for (int j = L ; j <= R ; j++) {
                tcnt[a[j]]++;
                if (tcnt[a[j]] > tcnt[0] || (tcnt[a[j]] == tcnt[0] && ind[a[j]] < ans)) {
                    ans = ind[a[j]];
                    tcnt[0] = tcnt[a[j]];
                }
            }
            cout << ans << "\n";
            for (int j = L ; j <= R ; j++) {
                tcnt[a[j]]--;
            }
            tcnt[0] = 0;
            continue;
        }
        int tx = x + 1, ty = y - 1;
        int tmode = mode[tx][ty];
        int tcnt = cnt[tx][ty][0];
        for (int j = L ; j <= ed[x] ; j++) { // 把左边多余部分加进来
            add(tx, ty, j);
        }
        for (int j = st[y] ; j <= R ; j++) { // 把右边多余部分加进来
            add(tx, ty, j);
        }
        ans = mode[tx][ty];
        cout << ans << "\n";
        for (int j = L ; j <= ed[x] ; j++) { // 删去左边多余部分
            del(tx, ty, j);
        }
        for (int j = st[y] ; j <= R ; j++) { // 删去右边多余部分
            del(tx, ty, j);
        }
        mode[tx][ty] = tmode; // 复原众数
        cnt[tx][ty][0] = tcnt; // 复原数量
    }
    return 0;
}