P13698 「CyOI」追忆 题解

· · 题解

传送门： P13698

先把所有点按照权值 a_i 排序得到一个排列 p_i，也即做离散化。为了方便处理，将所有 1 类修改操作离线下来，对于第 i 次 1 修改，若在其后出现了 c 次复制操作，就将这次修改的 k 更改为 k2^c。我们的目标是求出每次 1 类操作后的中位数，设 len_i 表示第 i 次操作后 D 的长度。

经典思路是将 p_i 按照块长 B = \Theta(\sqrt{n}) 分块，对每次询问先求出中位数所在的块，然后再枚举块中的每个点检查是否是答案。

对于整块查询，记第 i 块的左右端点为 l_i,r_i，对每一块 i 以及前 j 次修改求出 f_{i,j} 表示 p_{1,\dots,r_i} 在前 j 修改中共被加入 D 中 f_{i,j} 次，找到最小的 j 满足 f_{i,j} \ge \lceil \dfrac{len_j}{2} \rceil。对每个 i 求出 sum_u 表示树上从点 u 到点 1 的路径上出现了 sum_u 个 p_{1,\dots,r_i} 中的点即可 O(n\sqrt{n}) 求出所有的 f_{i,j}。

对于散点检查，我们需要求出一个点 u 在前 j 次修改中被加入的次数。依次枚举修改 u,v,k，则路径 u\rightarrow v 上的点加入次数 +k。差分后支持单点加，查询区间和即可。由于修改次数为 O(n)，查询次数为 O(n\sqrt{n})，依然按 B 分块后平衡为单次修改 O(\sqrt{n})，单次查询 O(1) 即可。

时间复杂度 O(n\sqrt{n})，将处理整块的过程离线即可做到空间复杂度 O(n)。

关于强制在线版本复杂度下界的一个证明

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

typedef long long ll;
const int N = 1e5+5;
const int B = 1500;
const int Mod = 998244353;

int n, m, a[N], id[N];
int nfd[N], dfn[N], ct[N], f[N], dep[N], siz[N], hs[N];

vector<int> T[N];

void dfs1(int x, int fa) {
    f[x] = fa;
    dep[x] = dep[fa] + 1;
    siz[x] = 1;
    for (auto s : T[x]) {
        if (s == fa) continue;
        dfs1(s, x);
        siz[x] += siz[s];
        if (siz[s] >= siz[hs[x]]) hs[x] = s;
    }
}

void dfs2(int x, int ctop) {
    ct[x] = ctop;
    nfd[dfn[x] = ++dfn[0]] = x;
    if (hs[x]) dfs2(hs[x], ctop);
    for (auto s : T[x]) {
        if (s == f[x] || s == hs[x]) continue;
        dfs2(s, s);
    }
}

inline int lca(int u, int v) {
    while (ct[u] != ct[v]) {
        if (dep[ct[u]] < dep[ct[v]]) swap(u, v);
        u = f[ct[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

inline int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)] + 1; }

struct op {
    int u, v, l;
    ll k;
    op() {}
    op(ll _k, int _v, int _u): u(_u), v(_v), k(_k) { l = lca(_u, _v); }
} P[N];

int qry_p[N], db_p[N], st[N], ans[N];
int bl[N / B + 5], br[N / B + 5], sum[N];
bitset<N> v;
ll nd[N];

namespace B1 {//O(sqrt(n))单点加，O(1)区间和
    const int B = 330;

    ll sb[N / B + 5], s[N + B];
    inline void add(int x, ll k) {
        int xb = x / B;
        for (int i = xb + 1; i <= n / B; i++) sb[i] += k;
        for (int i = x; i / B == xb; i++) s[i] += k;
    }
    inline ll qry(int x) { return sb[x / B] + s[x]; }

    inline void upd(op p) {
        add(dfn[p.u], p.k);
        add(dfn[p.v], p.k);
        add(dfn[p.l], -p.k);
        if (f[p.l]) add(dfn[f[p.l]], -p.k);
    }
}

int main() {
    n = read();

    for (int i = 1; i <= n; i++) a[i] = read(), id[i] = i;

    sort(id + 1, id + n + 1, [](int x, int y) { return a[x] < a[y]; });

    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        T[u].pb(v);
        T[v].pb(u);
    }

    dfs1(1, 0);
    dfs2(1, 1);

    int _ = read();
    ll cl = 0;
    while (_--) {
        int o = read();
        if (o == 1) P[++m] = op(read(), read(), read());
        else if (o == 2) qry_p[m]++;
        else db_p[m]++;
    }

    for (ll i = m, t = 1; i; i--) {
        while (db_p[i]--) t <<= 1;
        P[i].k *= t;
    }
    for (int i = 1; i <= m; i++)
        cl += P[i].k * dis(P[i].u, P[i].v), nd[i] = (cl + 1) / 2;

    for (int i = 0; i <= n / B; i++) {
        bl[i] = max(1, i * B);
        br[i] = min(n, i * B + B - 1);

        for (int j = bl[i]; j <= br[i]; j++) v[id[j]] = 1;
        for (int j = 1; j <= n; j++) sum[nfd[j]] = sum[f[nfd[j]]] + v[nfd[j]];
        for (int j = bl[i]; j <= br[i]; j++) v[id[j]] = 0;

        cl = 0;
        for (int j = 1; j <= m; j++) {
            cl += P[j].k * (sum[P[j].u] + sum[P[j].v] - sum[P[j].l] - sum[f[P[j].l]]);
            if (!st[j] && qry_p[j]) {
                if (nd[j] > cl) nd[j] -= cl;
                else st[j] = bl[i];
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        B1::upd(P[i]);

        if (qry_p[i]) {
            for (int j = st[i]; ; j++) {
                cl = B1::qry(dfn[id[j]] + siz[id[j]] - 1) - B1::qry(dfn[id[j]] - 1);
                if (nd[i] > cl) nd[i] -= cl;
                else { ans[i] = id[j]; break; }
            }
        }
    }

    for (int i = 0; i <= m; i++) while (qry_p[i]--) printf("%d\n", a[ans[i]]);
    return 0;
}