洒水器 & 毛毛虫剖分

· · 算法·理论

树上邻域信息的常见维护方式。这里的信息具有结合律,但不一定具有交换律和逆元。

洒水器

简单来说就是打标记,可以和线段树一类的数据结构配合,但是缺点是只能单点查。

P9527 [JOIST 2022] 洒水器 / Sprinkler

给出一棵 n 个节点的无根树,点有点权 a_i。q 次操作:

  1. 给出 u,k,x,将距离 u 不超过 k 的点的点权乘 x。
  2. 给出 u,查询 u 的点权。

对给出的模数取模,不保证模数为质数。

在树上每个节点维护若干标记:将 u 子树中距离恰为 i 的点乘上 f_{i,u}。

修改时对这些标记进行更新:f_{u,k}, f_{u,k-1}, f_{\operatorname{fa}(u),k-2},f_{\operatorname{fa}(u),k-3},\cdots,显然只会做 O(k) 次。

标记下传很困难,因此永久化。查询时需要跳父亲来得到标记。也只会跳 O(k) 次。

这个做法可以做到不重不漏。复杂度 O(n+qk)。

::::info[代码]

const int N = 2e5 + 5;
int n, _mod, q, fa[N];
vector<int> e[N];
mint a[N], tag[41][N];

void dfs(int u) {
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        fa[v] = u, dfs(v);
    }
}

void _main() {
    cin >> n >> _mod, mint::set_mod(_mod);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> a[i];
    fa[1] = -1, dfs(1);
    for (int i = 0; i <= 40; i++) fill(tag[i], tag[i] + n + 1, 1);
    cin >> q;
    for (int opt, u, k, x; q--; ) {
        cin >> opt >> u;
        if (opt == 1) {
            cin >> k >> x;
            for (int i = 0; i <= k; i++, u = fa[u]) {
                if (fa[u] == -1) {
                    for (int d = 0; d <= k - i; d++) tag[d][u] *= x;
                    break;
                }
                tag[k - i][u] *= x;
                if (k - i - 1 >= 0) tag[k - i - 1][u] *= x;
            }
        } else {
            mint res = a[u];
            for (int i = 0; i <= 40 && u != -1; i++, u = fa[u]) res *= tag[i][u];
            cout << res << '\n';
        }
    }
}

::::

毛毛虫剖分

魔改重链剖分中 DFS 序的编号方式。可以实现 HLD 的常用操作,缺点是码量大,只能维护 1 邻域。

【模板】毛毛虫剖分

给出一棵 n 个节点的有根树,节点从 1 \sim n 编号,根节点为 1。每个节点有一个点权 a_i,你需要支持 q 次操作:

  • 1 u v c:将 u 到 v 的树链加上 c;
  • 2 u c:将 u 的子树加上 c;
  • 3 u v c:将与 u 到 v 的树链邻接的点加上 c;
  • 4 u v:求从 u 到 v 的树链点权和;
  • 5 u:求 u 子树的点权和;
  • 6 u v:求与 u 到 v 的树链邻接的点的点权和。

重剖的第一个 DFS 不动。对于重链顶 u,我们给出如下标号方式:

这样的标号具有如下性质:

套线段树维护即可,复杂度 O(q\log^2 n)。

:::::info[代码]

const int N = 3e5 + 5;
int n, q, a[N];
vector<int> e[N];

int dn, sz[N], fa[N], dep[N], son[N], top[N], bot[N], dfn[N], rev[N], sl[N], sr[N], subl[N], subr[N];
void dfs1(int u) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        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;
    if (u != t) return;
    int w = u;
    for (; son[w]; w = son[w]) top[son[w]] = t, dfn[son[w]] = ++dn;
    bot[t] = w;
    for (w = u; w; w = son[w]) {
        sl[w] = dn + 1;
        for (int v : e[w]) {
            if (v != fa[w] && v != son[w]) dfn[v] = ++dn;
        }
        sr[w] = dn;
    }
    for (w = u; w; w = son[w]) {
        subl[w] = dn + 1;
        for (int v : e[w]) {
            if (v != fa[w] && v != son[w]) dfs2(v, v);
        }
        subr[w] = dn;
    }
}

struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    i64 sum[N << 2], add[N << 2];
    void pushup(int rt) {sum[rt] = sum[ls] + sum[rs];}
    void apply(int rt, i64 c, int len) {sum[rt] += c * len, add[rt] += c;}
    void pushdown(int rt, int ln, int rn) {
        if (add[rt]) apply(ls, add[rt], ln), apply(rs, add[rt], rn), add[rt] = 0;
    }
    void build(int l = 1, int r = n, int rt = 1) {
        if (l == r) return sum[rt] = rev[l], void();
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
    }
    void update(int tl, int tr, i64 c, int l = 1, int r = n, int rt = 1) {
        if (tl <= l && r <= tr) return apply(rt, c, r - l + 1), void();
        int mid = (l + r) >> 1; pushdown(rt, mid - l + 1, r - mid);
        if (tl <= mid) update(tl, tr, c, l, mid, ls);
        if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
        pushup(rt); 
    }
    i64 ask(int tl, int tr, int l = 1, int r = n, int rt = 1) {
        if (tl <= l && r <= tr) return sum[rt];
        int mid = (l + r) >> 1; pushdown(rt, mid - l + 1, r - mid);
        if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs);
        return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs);
    }
} S;

void addp(int u, int v, i64 c) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        int x = top[u], y = u;
        S.update(dfn[x], dfn[x], c);
        if (x != y) S.update(dfn[son[x]], dfn[y], c);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    int x = v, y = u;
    if (x == top[x]) {
        S.update(dfn[x], dfn[x], c);
        if (x != y) S.update(dfn[son[x]], dfn[y], c);
    } else {
        S.update(dfn[x], dfn[y], c);
    }
}
void adds(int u, i64 c) {
    int x = u, y = bot[top[u]];
    if (x == top[x]) {
        S.update(dfn[x], dfn[x], c);
        if (x != y) S.update(dfn[son[x]], dfn[y], c);
    } else {
        S.update(dfn[x], dfn[y], c);
    }
    if (sl[x] <= sr[y]) S.update(sl[x], sr[y], c);
    if (subl[x] <= subr[y]) S.update(subl[x], subr[y], c);
}
void addc(int u, int v, i64 c) {
    int lu = 0, lv = 0;
    auto upd = [&](int l, int r, int p1, int p2, i64 c) -> void {
        if (l > r) return;
        vector<int> p = {l - 1, r + 1};
        if (l <= p1 && p1 <= r) p.emplace_back(p1);
        if (l <= p2 && p2 <= r && p2 != p1) p.emplace_back(p2);
        sort(p.begin(), p.end());
        for (int i = 0; i < (int)p.size() - 1; i++) {
            if (p[i] + 1 <= p[i + 1] - 1) S.update(p[i] + 1, p[i + 1] - 1, c); 
        }
    };
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(lu, lv);
        int x = top[u], y = u;
        S.update(dfn[x], dfn[x], c);
        if (x != y) S.update(dfn[son[x]], dfn[y], c);
        upd(sl[x], sr[y], dfn[lu], -1, c);
        if (son[u]) S.update(dfn[son[u]], dfn[son[u]], c);
        lu = x, u = fa[x];
    }
    if (dep[u] < dep[v]) swap(u, v), swap(lu, lv);
    if (v == top[v]) {
        S.update(dfn[v], dfn[v], c);
        if (u != v) S.update(dfn[son[v]], dfn[u], c);
    } else {
        S.update(dfn[v], dfn[u], c);
    }
    upd(sl[v], sr[u], dfn[lu], dfn[lv], c);
    if (son[u]) S.update(dfn[son[u]], dfn[son[u]], c);
    if (fa[v]) S.update(dfn[fa[v]], dfn[fa[v]], c);
}

i64 askp(int u, int v) {
    i64 res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        int x = top[u], y = u;
        res += S.ask(dfn[x], dfn[x]);
        if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    int x = v, y = u;
    if (x == top[x]) {
        res += S.ask(dfn[x], dfn[x]);
        if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
    } else {
        res += S.ask(dfn[x], dfn[y]);
    } return res;
}
i64 asks(int u) {
    i64 res = 0;
    int x = u, y = bot[top[u]];
    if (x == top[x]) {
        res += S.ask(dfn[x], dfn[x]);
        if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
    } else {
        res += S.ask(dfn[x], dfn[y]);
    }
    if (sl[x] <= sr[y]) res += S.ask(sl[x], sr[y]);
    if (subl[x] <= subr[y]) res += S.ask(subl[x], subr[y]);
    return res;
}
i64 askc(int u, int v) {
    i64 res = 0;
    int lu = 0, lv = 0;
    auto upd = [&](int l, int r, int p1, int p2) -> void {
        if (l > r) return;
        vector<int> p = {l - 1, r + 1};
        if (l <= p1 && p1 <= r) p.emplace_back(p1);
        if (l <= p2 && p2 <= r && p2 != p1) p.emplace_back(p2);
        sort(p.begin(), p.end());
        for (int i = 0; i < (int)p.size() - 1; i++) {
            if (p[i] + 1 <= p[i + 1] - 1) res += S.ask(p[i] + 1, p[i + 1] - 1); 
        }
    };
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(lu, lv);
        int x = top[u], y = u;
        res += S.ask(dfn[x], dfn[x]);
        if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
        upd(sl[x], sr[y], dfn[lu], -1);
        if (son[u]) res += S.ask(dfn[son[u]], dfn[son[u]]);
        lu = x, u = fa[x];
    }
    if (dep[u] < dep[v]) swap(u, v), swap(lu, lv);
    if (v == top[v]) {
        res += S.ask(dfn[v], dfn[v]);
        if (u != v) res += S.ask(dfn[son[v]], dfn[u]);
    } else {
        res += S.ask(dfn[v], dfn[u]);
    }
    upd(sl[v], sr[u], dfn[lu], dfn[lv]);
    if (son[u]) res += S.ask(dfn[son[u]], dfn[son[u]]);
    if (fa[v]) res += S.ask(dfn[fa[v]], dfn[fa[v]]);
    return res;
}

void _main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    dfs1(1), dfn[1] = ++dn, dfs2(1, 1);
    for (int i = 1; i <= n; i++) rev[dfn[i]] = a[i];
    S.build();
    for (int opt, u, v, c; q--; ) {
        cin >> opt;
        if (opt == 1) cin >> u >> v >> c, addp(u, v, c);
        else if (opt == 2) cin >> u >> c, adds(u, c);
        else if (opt == 3) cin >> u >> v >> c, addc(u, v, c);
        else if (opt == 4) cin >> u >> v, cout << askp(u, v) << '\n';
        else if (opt == 5) cin >> u, cout << asks(u) << '\n';
        else if (opt == 6) cin >> u >> v, cout << askc(u, v) << '\n';
    }
}

:::::