题解：「CyOI」追忆

· · 题解

Solution

暴打官解。我们将操作二加强为求第 k 小，然后先忽略操作三。

将 a_i 离散化为 1\sim n，值域分块，每 \sqrt{n} 个一块。对于一个块，内部维护这些点组成的虚树，再维护这些点的值在 D 出现几次。查询时从小到大枚举块，求出所在块之后再确定具体值。

我们考虑要维护怎么样的东西：

修改直接树上差分，然后更新所有点的点权和，散块时 DFS 一遍算出具体值即可。

那操作三怎么办呢？考虑有意义（即操作时 D 非空）的操作三只有 \log10^{18}\le 60 次，每次操作三直接把所有点的差分值乘上 2 即可。

复杂度 \mathcal O((n+q)\sqrt n+n\log V)。离线逐块处理则空间线性。

:::info[代码] 提交记录。

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 1e5 + 5, B = 316;
    struct qry { int o, x, y, z; LL p; } Q[N];
    int n, q, ct, x, y, a[N], o[N], dfn[N], id[N], vs[N], up[N], fa[N], st[20][N];
    vector<int> s, G[N], E[N]; LL sm, d[N], t[N], c[N], w[N];
    void dfs1(int x) {
        dfn[x] = ++ ct, id[ct] = x, st[0][ct] = dfn[fa[x]];
        for (int y : G[x])
            if (y != fa[x]) fa[y] = x, d[y] = d[x] + 1, dfs1(y);
    }
    int lca(int x, int y) {
        if (x == y) return x;
        if ((x = dfn[x]) > (y = dfn[y])) swap(x, y);
        int d = __lg(y - x ++);
        return id[min(st[d][x], st[d][y - (1 << d) + 1])];
    }
    int main() {
        cin >> n;
        REP(i, 1, n) cin >> a[i], o[i] = t[i] = i;
        REP(i, 2, n) cin >> x >> y, G[x].pb(y), G[y].pb(x);
        d[1] = 1, dfs1(1);
        REP(i, 1, __lg(n)) REP(j, 1, n - (1 << i) + 1)
            st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        cin >> q;
        REP(i, 1, q) {
            cin >> Q[i].o;
            if (Q[i].o == 1) {
                cin >> Q[i].x >> Q[i].y >> Q[i].z, Q[i].p = lca(Q[i].x, Q[i].y);
                sm += (d[Q[i].x] + d[Q[i].y] - d[Q[i].p] - d[fa[Q[i].p]]) * Q[i].z;
            }
            if (Q[i].o == 2) Q[i].p = (sm + 1) / 2;
            if (Q[i].o == 3) sm *= 2;
        }
        sort(o + 1, o + 1 + n, [&](int x, int y) { return a[x] < a[y]; });
        sort(t + 1, t + 1 + n, [&](int x, int y) { return dfn[x] < dfn[y]; });
        for (int l = 1, r = min(B, n); l <= n; ) {
            REP(i, 1, n) c[i] = vs[i] = 0, E[i].clear();
            REP(i, l, r) vs[o[i]] = 1;
            DEP(i, n, 1) {
                int x = t[i];
                if (c[x] > 1 && !vs[x]) vs[x] = 2;
                if (c[x] > 0 || vs[x]) c[fa[x]] ++;
            }
            REP(i, 1, n) {
                int x = t[i];
                up[x] = (vs[x] ? x : up[fa[x]]), c[x] = 0;
            }
            sm = 0, s.clear();
            REP(i, 1, n) {
                if (!vs[i]) continue;
                int x = up[fa[i]]; s.pb(i);
                if (x) E[x].pb(i), E[i].pb(x);
            }
            sort(ALL(s), [&](int x, int y) { return dfn[x] < dfn[y]; });
            for (int x : s)
                d[x] = d[up[fa[x]]] + (vs[x] == 1);
            reverse(ALL(s));
            REP(i, 1, q) {
                if (Q[i].o == 1) {
                    int x = up[Q[i].x], y = up[Q[i].y], z = Q[i].z, p = up[Q[i].p], q = up[fa[Q[i].p]];
                    sm += (d[x] + d[y] - d[p] - d[q]) * z;
                    c[x] += z, c[y] += z, c[p] -= z, c[q] -= z;
                }
                if (Q[i].o == 2) {
                    if (Q[i].p <= 0) continue;
                    if (Q[i].p > sm) { Q[i].p -= sm; continue; }
                    for (int x : s) w[x] = c[x];
                    for (int x : s) w[up[fa[x]]] += w[x];
                    REP(j, l, r) {
                        Q[i].p -= w[o[j]];
                        if (Q[i].p <= 0) { Q[i].x = a[o[j]]; break; }
                    }
                }
                if (Q[i].o == 3) {
                    if (!sm) continue;
                    sm *= 2;
                    for (int x : s) c[x] *= 2;
                }
            }
            l = r + 1, r = min(r + B, n);
        }
        REP(i, 1, q)
            if (Q[i].o == 2) cout << Q[i].x << '\n';
        return 0;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}

:::