蒲公英

AcWing-249-蒲公英

分析

见《进阶指南》第227页。

实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 40010, T = 800;
int n, a[N], m;
int tot, nums[N];
vector<int> indexes_of[N];
int pos[N], L[T], R[T];
int c[N];
int f[T][T];

void discrete () {
    for (int i = 1; i <= n; ++ i) nums[i] = a[i];
    sort(nums + 1, nums + n + 1);
    tot = unique(nums + 1, nums + n + 1) - (nums + 1);
}
int ask (int x) {
    return lower_bound(nums + 1, nums + tot + 1, x) - nums;
}
void initialize () {
    discrete();
    for (int i = 1; i <= n; ++ i) a[i] = ask(a[i]);
    for (int i = 1; i <= n; ++ i) indexes_of[a[i]].push_back(i);

    int t = sqrt(n * log2(n));
    int length = (n == 1 ? n : n / t);
    for (int i = 1; i <= t; ++ i) {
        L[i] = (i - 1) * length + 1;
        R[i] = i * length;
    }
    if (R[t] < n) {
        ++ t;
        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;
    
    for (int i = 1; i <= t; ++ i) {
        memset(c, 0, sizeof(c));
        int val = 0, cnt = 0;
        for (int j = L[i]; j <= n; ++ j) {
            ++ c[a[j]];
            if (c[a[j]] > cnt || (c[a[j]] == cnt && a[j] < val)) {
                val = a[j];
                cnt = c[a[j]];
            }
            f[i][pos[j]] = val;
        }
    }
}
void update (int x, int l, int r, int& val, int& cnt) {
    int count_x = upper_bound(indexes_of[x].begin(), indexes_of[x].end(), r)
        - lower_bound(indexes_of[x].begin(), indexes_of[x].end(), l);
    if (count_x > cnt || (count_x == cnt && x < val)) {
        val = x;
        cnt = count_x;
    }
}
int query (int l, int r) {
    int val = 0, cnt = 0;
    int x = pos[l], y = pos[r];
    if (x == y) {
        for (int i = l; i <= r; ++ i) update(a[i], l, r, val, cnt);
        return nums[val];
    }
    if (f[x + 1][y - 1] >= 1) update(f[x + 1][y - 1], l, r, val, cnt); // 1 ≤ ai ≤ 1e9
    for (int i = l; i <= R[x]; ++ i) update(a[i], l, r, val, cnt);
    for (int i = L[y]; i <= r; ++ i) update(a[i], l, r, val, cnt);
    return nums[val];
}

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

    initialize();
    int x = 0;
    while (m --) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + x - 1) % n + 1; // 强制在线
        r = (r + x - 1) % n + 1;
        if (l > r) swap(l, r);
        x = query(l, r);
        printf("%d\n", x);
    }
    return 0;
}