P4556 雨天的尾巴

大名鼎鼎的线段树合并模板题。

题意简述

给定一棵 $n$ 个节点的树。处理 $m$ 次修改，每次给定一个 $x,y,z$ ，表示给 $\delta(x,y)$ 这条路径上所有的节点发一份 $z$ 类型的救济粮，最后要求输出每个节点内救济粮最多的那个种类。

范围： $1\le n,m\le10^5$ ， $1\le x,y\le n$ ， $1\le z\le10^5$ 。

思路

首先涉及到修改树上的一条路径，显然考虑用树上差分维护救济粮数量。每次修改让 $x,y$ 对应的 $z$ 救济粮的计数器 $+1$ ， $\text{LCA}(x,y),f(\text{LCA}(x,y))$ 的 $z$ 救济粮计数器 $+1$ 。然后某节点救济粮的真正数量就是其子树和。
我们人为地规定根为 $1$ 。
那么怎么快速地维护 “某节点救济粮最多的是哪种” 呢？考虑使用 “线段树二分”。我们对每个节点建立一个线段树，维护 $[1,10^5]$ 上每种救济粮有多少。显然这样暴力开要 MLE，那么我们用动态开点线段树就好了。

具体来说，线段树的每个节点维护两个变量：kind 和 amount。kind 表示该节点管辖的区间内哪种救济粮最多，amount 表示最多的救济粮有多少。pushup() 这样写：

void pushup(int cur) {
    // 左儿子的 kind 总是小于右儿子的
    if (nodes[nodes[cur].ls].amount >= nodes[nodes[cur].rs].amount) {
        nodes[cur].amount = nodes[nodes[cur].ls].amount;
        nodes[cur].kind = nodes[nodes[cur].ls].kind;
    } else {
        nodes[cur].amount = nodes[nodes[cur].rs].amount;
        nodes[cur].kind = nodes[nodes[cur].rs].kind;
    }
}

对于叶子节点，kind 和 amount 就是“原始数据”了。
如何快速地统计子树和？用线段树合并就好了。我们不断向下 DFS，合并线段树。我们搜到一个节点，当所有子节点的回溯都完成时，所有子节点也都合并（到当前节点）了，这时当前节点存的 kind 就是我们想要的答案。我们要一边合并一边记录答案。

合并的时候，具体这样写：

int merge(int l, int r, int a, int b) {
    if (not a) return b;
    if (not b) return a;
    if (l == r) {
        nodes[a].amount += nodes[b].amount;
        nodes[a].kind |= nodes[b].kind; // 重要！！！！！有可能 a 没有存放这种救济粮，kind 就没设置过！！！
    } else {
        int m = l + ((r - l) >> 1);
        nodes[a].ls = merge(l ,m, nodes[a].ls, nodes[b].ls);
        nodes[a].rs = merge(m + 1, r, nodes[a].rs, nodes[b].rs);
        pushup(a);
    }
    return a;
}

注意一下注释的地方就好了。我卡了很久（ $75pts$ ）。

编码

用时 4.56 s 内存 149.30 MB

/*
* P4556 [Vani有约会] 雨天的尾巴 [模板] 线段树合并
*/
#include <iostream>
using namespace std;
const int MAXN = 1e5;
// 前向星
struct Edge {
    int to, nxt;
} edges[MAXN << 1 | 1];
int head[MAXN + 1], ans[MAXN + 1];
int ecnt = 1; // 不能用 0
void addedge(int u, int v) {
    edges[ecnt].nxt = head[u];
    edges[ecnt].to = v;
    head[u] = ecnt++;
}
// 动态开点线段树 (每个节点维护一个)
const int MAXZ = 1e5; // z 的值域
struct Node {
    int amount;    // 最多的粮有多少
    int kind;      // 最多的粮是哪种
    int ls, rs;
} nodes[MAXZ*40*4];
int ncnt = 1; // 不可以为 0，因为 seg[i] 初值就是 0
int seg[MAXN + 1]; // seg[i] 表示节点 i 的线段树的根

void pushup(int cur) {
    // 左儿子的 kind 总是小于右儿子的
    if (nodes[nodes[cur].ls].amount >= nodes[nodes[cur].rs].amount) {
        nodes[cur].amount = nodes[nodes[cur].ls].amount;
        nodes[cur].kind = nodes[nodes[cur].ls].kind;
    } else {
        nodes[cur].amount = nodes[nodes[cur].rs].amount;
        nodes[cur].kind = nodes[nodes[cur].rs].kind;
    }
}
// 仅仅是创建儿子节点罢了
void pushdown(int cur) {
    if (not nodes[cur].ls) nodes[cur].ls = ncnt++;
    if (not nodes[cur].rs) nodes[cur].rs = ncnt++;
}
// 让 node 节点 z 种类救济粮数量增加 y
void add(int node, int z, int y, int l, int r, int cur = 0) {
    if (cur == 0) { // 这个写法可能有点奇怪
        if (not seg[node]) seg[node] = ncnt++;
        cur = seg[node];
    }
    if (l == r) {
        nodes[cur].amount += y;
        // 理论上只赋值一次就行了，这里无脑赋值也行吧（有点迷惑）
        nodes[cur].kind = z;
    } else {
        int m = l + ((r - l) >> 1);
        pushdown(cur);
        if (z <= m) add(node, z, y, l, m, nodes[cur].ls);
        else add(node, z, y, m + 1, r, nodes[cur].rs);
        pushup(cur);
    }
}
// 线段树合并 a, b 分别是两棵树的节点
// 注意是把 b 合并到 a
int merge(int l, int r, int a, int b) {
    if (not a) return b;
    if (not b) return a;
    if (l == r) { // 递归终点
        nodes[a].amount += nodes[b].amount;
        nodes[a].kind |= nodes[b].kind; // 巨坑无比！！！75pts在这卡了好久
    } else {
        int m = l + ((r - l) >> 1);
        nodes[a].ls = merge(l, m, nodes[a].ls, nodes[b].ls);
        nodes[a].rs = merge(m + 1, r, nodes[a].rs, nodes[b].rs);
        pushup(a);
    }
    return a;
}

// 再写一个 LCA，用倍增就行了
int depth[MAXN + 1], Log2[MAXN + 1];
bool vis[MAXN + 1];
int fa[17][MAXN + 1]; // 提高缓存命中率(玄学)；log2(1e5)~16.6
void initlca(int rt, int par = 0) { // dfs
    vis[rt] = true;
    depth[rt] = par ? depth[par] + 1 : 0;
    fa[0][rt] = par; // 边界条件
    for (int i = 1; i < 17; i++) {
        fa[i][rt] = fa[i - 1][fa[i - 1][rt]];
    }
    for (int e = head[rt]; e; e = edges[e].nxt) { // dfs 咯
        if (not vis[edges[e].to]) {
            initlca(edges[e].to, rt);
        }
    }
}
int getlca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b); // 保证 a 更深
    while (depth[a] > depth[b]) {
        a = fa[Log2[depth[a] - depth[b]]][a];
    }
    if (a == b) return a;
    for (int i = Log2[depth[a]]; i >= 0; i--) {
        if (fa[i][a] != fa[i][b]) {
            a = fa[i][a], b = fa[i][b];
        }
    }
    return fa[0][a];
}

// 理论上这也是线段树的部分，但是要用到 fa[][] 所以调到这了
// 合并树上所有点的线段树
void mergeall(int rt) {
    for (int e = head[rt]; e; e = edges[e].nxt) {
        if (edges[e].to == fa[0][rt]) continue; // 不用 vis[] 了
        mergeall(edges[e].to); // 先向下搜索
        // 不用启发式能过吗
        seg[rt] = merge(1, MAXZ, seg[rt], seg[edges[e].to]); // 不能忽略返回值！！！
    }
    // 叶子节点会直接跳到这里
    if (nodes[seg[rt]].amount) ans[rt] = nodes[seg[rt]].kind;
}

int main() {
    int n, m, x, y, z;
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) { // 树是 n-1 条边！！！
        cin >> x >> y;
        addedge(x, y);
        addedge(y, x);
    }
    for (int i = 2; i <= n; i++) {
        Log2[i] = Log2[i >> 1] + 1;
    }
    initlca(1); // 随便定一个根就好
    int lca;
    while (m--) {
        cin >> x >> y >> z;
        lca = getlca(x, y); // 不用记忆化吧...
        add(x, z, 1, 1, MAXZ);
        add(y, z, 1, 1, MAXZ);
        add(lca, z, -1, 1, MAXZ);
        add(fa[0][lca], z, -1, 1, MAXZ);
    }
    mergeall(1); // 激动人心的合并环节
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

题意简述​

思路​

编码​

题意简述

思路

编码