P7172

Xycxxx · 2026-05-08 18:48:14 · 题解

将所有的 a_i 和叶子当作关键点。

考虑把 2 度点的链缩成一个点，此时点数是 \mathcal{O}(n) 的。

则链上深度最大的点即为关键点。

此时原问题转化为求 u,v 缩点后的的最近公共祖先对应链的深度最大的点，注意如果 u,v 存在祖先关系要特殊处理。

考虑自底向上建树，维护每条链深度最大的点编号，初始时将所有叶子存下来，然后加入第 i 层的点，先继承上一层的信息，然后将第 a_i 个位置维护的深度最大的点改成 a_i，将第 a_i+1 个点删掉即可。主席树维护即可，查位置可以线段树二分。

复杂度 \mathcal{O}(n\log n)。

#include <bits/stdc++.h>
#define int long long
#define rd read()
using namespace std;
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int N = 5e5 + 5;
int n, q, t, a[N], tot, rt[N], w[N], idx, f[20][N], dep[N], lst;
map<int, int> mp;
vector<int> g[N];
struct Node {int lc, rc, s, id;} tr[N * 55];
inline int get(int x) {return x * (x + 1) / 2;}
inline int gt(int x) {
    if (!mp[x]) w[mp[x] = ++idx] = x;
    return mp[x];
}
inline void pushup(int k) {tr[k].s = tr[tr[k].lc].s + tr[tr[k].rc].s;}
inline void add(int &k, int l, int r, int p, int v, int lst) {
    tr[k = ++tot] = tr[lst]; 
    if (l == r) return tr[k] = {0, 0, (v > 0), v}, void();
    int mid = l + r >> 1; mid >= p ? add(tr[k].lc, l, mid, p, v, tr[lst].lc) : add(tr[k].rc, mid + 1, r, p, v, tr[lst].rc);
    pushup(k);
}
inline pair<int, int> ask(int k, int l, int r, int id) {
    if (l == r) return {tr[k].id, l}; int mid = l + r >> 1; 
    return (tr[tr[k].lc].s >= id ? ask(tr[k].lc, l, mid, id) : ask(tr[k].rc, mid + 1, r, id - tr[tr[k].lc].s));
}
void dfs(int u) {
    dep[u] = dep[f[0][u]] + 1;
    for (int i = 1; i <= 19; ++i) f[i][u] = f[i - 1][f[i - 1][u]];
    for (auto v : g[u]) f[0][v] = u, dfs(v);
}
inline int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 19; ~i; --i) if (dep[f[i][u]] >= dep[v]) u = f[i][u];
    if (u == v) return v;
    for (int i = 19; ~i; --i) if (f[i][u] ^ f[i][v]) u = f[i][u], v = f[i][v];
    return f[0][u];
}
inline int ask(int u, int v) {
    int t1 = sqrt(2 * u), t2 = sqrt(2 * v);
    t1 += (get(t1) < u), t2 += (get(t2) < v);
    t1 = gt(ask(rt[t1], 1, n + 1, u - get(t1 - 1)).first);
    t2 = gt(ask(rt[t2], 1, n + 1, v - get(t2 - 1)).first);
    return min({u, v, w[lca(t1, t2)]});
}
signed main() {
    n = rd, q = rd, t = rd;
    for (int i = 1; i <= n; ++i) a[i] = rd;
    for (int i = 1; i <= n + 1; ++i) add(rt[n + 1], 1, n + 1, i, i + get(n), rt[n + 1]);
    for (int i = n; i; --i) {
        int rk = a[i] - get(i - 1);
        pair<int, int> x = ask(rt[i + 1], 1, n + 1, rk), y = ask(rt[i + 1], 1, n + 1, rk + 1);
        add(rt[i], 1, n + 1, x.second, a[i], rt[i + 1]), add(rt[i], 1, n + 1, y.second, 0, rt[i]);
        g[gt(a[i])].push_back(gt(x.first)), g[gt(a[i])].push_back(gt(y.first));
    }
    dfs(gt(1));
    for (int i = 1, x, y; i <= q; ++i) {
        x = (rd - 1 + t * lst) % get(n + 1) + 1;
        y = (rd - 1 + t * lst) % get(n + 1) + 1;
        cout << (lst = ask(x, y)) << '\n';
    }
    return 0;
}