P4168 75pts WA求调

#include <bits/stdc++.h>
using namespace std;

const int N = 40010;
const int T = 210;

int n, m, t, K;
int a[N], b[N];
int pos[N], d[T][T], cnt[N], num[T][T];
int L[T], R[T];
vector<int> v[N];

int find_id(int x) {
    return lower_bound(b + 1, b + K + 1, x) - b;
}
// 统计值为 x 的下标在 [l..r] 内的个数
int get_count(int x, int l, int r) {
    auto &V = v[x];
    return upper_bound(V.begin(), V.end(), r) - lower_bound(V.begin(), V.end(), l);
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    // 离散化
    sort(b + 1, b + n + 1);
    K = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i <= n; i++) {
        a[i] = find_id(a[i]);
        v[a[i]].push_back(i);
    }
    // 选块大小 t
    t = sqrt(n);
    for(int i = 1; i <= t; i++) {
        L[i] = (i - 1) * t + 1;
        R[i] = i * t;
    }
    if(R[t] < n) L[++t] = R[t - 1] + 1, R[t] = n;
    // 每个位置属于哪个块
    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++)
            pos[j] = i;
    // 预处理：d[i][j] 表示从块 i 到块 j 的“众数”的压缩值，num[i][j] 为其出现次数
    for (int i = 1; i <= t; i++) {
        memset(cnt, 0, sizeof cnt);
        int best = 0, mx = 0;
        for(int j = L[i]; j <= n; j++) {
            int x = a[j];
            if(++cnt[x] > mx || cnt[x] == mx && x < best)
                mx = cnt[x], best = x;
            d[i][pos[j]] = best, num[i][pos[j]] = mx;
        }
    }
    // 在线查询
    int last_ans = 0;
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        // 防止“上一题答案影响下一题” 的技巧
        l = (l + last_ans - 1) % n + 1;
        r = (r + last_ans - 1) % n + 1;
        if (l > r) swap(l, r);

        int p = pos[l], q = pos[r];
        int ans = 0, maxx = 0;

        // 如果中间存在完整块
        if (p + 1 < q) ans = d[p + 1][q - 1], maxx = num[p + 1][q - 1];

        if(p == q) {
            // l, r 在同一块，直接暴力
            for (int i = l; i <= r; i++) {
                int tmp = get_count(a[i], l, r);
                if (tmp > maxx || tmp == maxx && a[i] < ans)
                    maxx = tmp, ans  = a[i];
            }
        } else {
            // 左边不满块区间
            for (int i = l; i <= R[p]; i++) {
                int tmp = get_count(a[i], l, r);
                if (tmp > maxx || tmp == maxx && a[i] < ans)
                    maxx = tmp, ans  = a[i];
            }
            // 右边不满块区间
            for (int i = L[q]; i <= r; i++) {
                int tmp = get_count(a[i], l, r);
                if (tmp > maxx || tmp == maxx && a[i] < ans)
                    maxx = tmp, ans  = a[i];
            }
        }
        printf("%d\n", b[ans]);
        last_ans = b[ans];
    }
    return 0;
}