【二分、树状数组】E - A += v

给定一个长度为 $N$ 的序列 $A$，元素取值在 $[1, M]$ 之间。执行 $10^{100}$ 次操作：每次选取 $A$ 中出现次数最少且数值最小的元素 $v$，将其追加到 $A$ 的末尾。给出 $Q$ 次独立查询，每次询问操作完成后第 $X_i$ 个位置的元素取值。数据范围：$N, M \le 5 \times 10^5, Q \le 2 \times 10^5, X_i \le 10^{18}$。

本题的核心在于洞察频率变化过程的周期性与单调性。初始状态下，序列长度为 $N$。设 $C[x]$ 为元素 $x$ 在初始序列中的出现次数，并记 $c_{max} = \max_{x \in [1, M]} C[x]$。

考虑操作的确定性机制：每次必然选取当前出现次数最小的元素，且数值较小者优先。这意味着元素的追加顺序严格遵循以 $(当前频率, 元素值)$ 为第一、第二关键字的字典序升序排列。由此可以建立分层模型：将元素的频率增加过程分为若干层。在第 $c$ 层中（$c \ge 0$），所有满足初始频率 $C[x] \le c$ 的元素 $x$ 将被依次追加一次，使得它们的频率提升至 $c+1$。当经历 $c_{max}$ 层后，所有 $M$ 个元素的频率均达到 $c_{max}$，此后整个序列将退化为严格的周期循环，即反复追加序列 $1, 2, \dots, M$。

基于上述分层模型，我们可以将查询按位置 $X_i$ 划分为两类：

1. 若目标位置落在前 $c_{max}$ 层内（即前缀非周期部分），可通过预处理各层的元素总数，计算其前缀和 $P$。对于给定的相对偏移量 $K = X_i - N$，利用二分查找快速定位其所属的层级 $c$ 及在该层中的相对位次 $r$。此时问题转化为：求所有满足 $C[x] \le c$ 的元素中，数值第 $r$ 小的元素。将所有此类查询按层级 $c$ 离线分组，并利用树状数组动态维护当前激活的元素集合，辅以树状数组上的倍增算法（Binary Lifting），即可在 $O(\log M)$ 的时间内高效响应查询。
2. 若目标位置落在 $c_{max}$ 层之后（即严格周期部分），由于周期长度固定为 $M$，且元素序列严格为 $1$ 到 $M$，直接利用同余运算取模即可得出答案。

综上，通过离线查询与动态维护结合，将复杂的无穷次操作转化为有限层内的二维偏序查询。

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

int n, m;
int a[500005];
int c[500005];
ll w[500005];
ll p[500005];
ll ans[200005];
int bit[500005];

struct Req {
    int pos;
    int id;
};

vector<int> gp[500005];
vector<Req> qu[500005];

void upd(int x, int v) {
    for (; x <= m; x += x & -x) bit[x] += v;
}

int kth(int r) {
    int id = 0;
    for (int i = 19; i >= 0; i--) {
        int nx = id + (1 << i);
        if (nx <= m && bit[nx] < r) {
            id = nx;
            r -= bit[id];
        }
    }
    return id + 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q;
    cin >> n >> m;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[a[i]]++;
    }
    for (int i = 1; i <= m; i++) {
        mx = max(mx, c[i]);
        gp[c[i]].push_back(i);
    }
    ll cur = 0;
    for (int i = 0; i <= n; i++) {
        cur += gp[i].size();
        w[i] = cur;
        if (i == 0) p[i] = w[i];
        else p[i] = p[i - 1] + w[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        ll x;
        cin >> x;
        if (x <= n) {
            ans[i] = a[x];
        } else {
            ll k = x - n;
            if (k > p[mx - 1]) {
                ll rem = (k - p[mx - 1] - 1) % m + 1;
                ans[i] = rem;
            } else {
                int l = 0, r = mx - 1;
                int res = 0;
                while (l <= r) {
                    int mid = l + (r - l) / 2;
                    if (p[mid] >= k) {
                        res = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                int pos = k;
                if (res > 0) pos -= p[res - 1];
                qu[res].push_back({pos, i});
            }
        }
    }
    for (int i = 0; i < mx; i++) {
        for (int x : gp[i]) upd(x, 1);
        for (Req qy : qu[i]) ans[qy.id] = kth(qy.pos);
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
    return 0;
}

时间复杂度：预处理层级与频率信息耗时 $O(N + M)$，树状数组的单点更新与倍增查询分别为 $O(\log M)$，共有 $Q$ 次离线查询与 $M$ 次元素激活更新，总时间复杂度为 $O(N + M + Q \log M)$。

空间复杂度：主要由各数组与离线查询记录开销构成，为 $O(N + M + Q)$。

https://atcoder.jp/contests/abc449/tasks/abc449_e