P5314 [Ynoi2011] ODT

· · 题解

我永远喜欢数据结构

题目传送门

  • 给出 n 个点的树和 q 次操作，点有点权，操作有两种类型：

不会全局平衡二叉树，但是两只 \log 跑得快。

重链剖分，考虑用树状数组维护点权的差分数组，用平衡树求第 y 小的点权。

考虑对于每个点维护其所有轻儿子的点权的平衡树，查询时暴力插入 / 删除父亲、重儿子以及它本身。

那么对于一次路径修改，只有路径上重链顶端的父亲的平衡树会受到修改。

所以每次先树状数组路径加，然后删除这些平衡树上原来的点权，插入新的点权即可。

时间复杂度为 \mathcal{O}(q\log ^2 n)，空间复杂度为 \mathcal{O}(n)。用了 pbds::tree，代码特别好写。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std; using namespace __gnu_pbds;
#define P pair<int, int>
#define fi first 
#define se second
#define eb emplace_back
#define ins insert
namespace lzyqwq {
    template<class T> void read(T &x) {
        x = 0; T f = 1; char c = getchar();
        for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
        for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
    }
    template<class T> void write(T x) {
        if (x > 9) write(x / 10); putchar(x % 10 + 48);
    }
    template<class T> void print(T x, char ed = '\n') {
        if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
    }
    const int N = 1e6 + 1; vector<int> g[N];
    int n, q, a[N], dep[N], top[N], dfn[N], sz[N], son[N], fa[N], cnt, id[N], ed[N];
    tree<P, null_type, less<P>, rb_tree_tag, 
         tree_order_statistics_node_update> tr[N];
    struct FenwickTree {
        int sum[N]; int B(int x) { return x & -x; }
        void M(int x, int v) { for (; x <= n; x += B(x)) sum[x] += v; }
        int Q(int x) { int r = 0; for (; x; x -= B(x)) r += sum[x]; return r; }
        void add(int l, int r, int d) { M(l, d); M(r + 1, -d); }
    } fwt;
    void dfs1(int u) {
        sz[u] = 1;
        for (int v : g[u])
            if (v != fa[u]) {
                dep[v] = dep[u] + 1; fa[v] = u; dfs1(v);
                sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v;
            }
    }
    void dfs2(int u, int t) {
        top[u] = t; dfn[u] = ++cnt; id[cnt] = u; 
        fwt.M(cnt, a[u] - a[id[cnt - 1]]); if (son[u]) dfs2(son[u], t);
        for (int v : g[u])
            if (v != fa[u] && v != son[u]) dfs2(v, v), tr[u].ins(P{a[v], v});
        ed[u] = cnt;
    }
    int val(int x) { return fwt.Q(dfn[x]); }
    void add(int u, int x, int y, bool op) {
        if (op) tr[u].ins(P{x, y}); else tr[u].erase(P{x, y});
    }
    void mdf(int x, int y, bool op) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            add(fa[top[x]], val(top[x]), top[x], op); x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y); 
        if (fa[x] && x != son[fa[x]]) add(fa[x], val(x), x, op);
    }
    void cadd(int x, int y, int v) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            fwt.add(dfn[top[x]], dfn[x], v); x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y); fwt.add(dfn[x], dfn[y], v);
    }
    void Main() {
        read(n); read(q); for (int i = 1; i <= n; ++i) read(a[i]);
        for (int i = 1, u, v; i < n; ++i) read(u), read(v), g[u].eb(v), g[v].eb(u);
        dfs1(1); dfs2(1, 1); 
        for (int op, x, y, v; q--;) {
            read(op); read(x); read(y);
            if (op & 1) read(v), mdf(x, y, 0), cadd(x, y, v), mdf(x, y, 1);
            else {
                add(x, val(x), x, 1); if (fa[x]) add(x, val(fa[x]), fa[x], 1); 
                if (son[x]) add(x, val(son[x]), son[x], 1); 
                print(tr[x].find_by_order(y - 1)->fi); 
                add(x, val(x), x, 0); if (fa[x]) add(x, val(fa[x]), fa[x], 0); 
                if (son[x]) add(x, val(son[x]), son[x], 0); 
            }
        }
    }
}
signed main() { return lzyqwq::Main(), 0; }