| 难度 | 算法s | 日期 | 题目链接 |
|---|---|---|---|
| 省选/NOI- | 线段树合并 | 2025-07-19 | https://luogu.com.cn/problem/4556 |
大名鼎鼎的线段树合并模板题。
题意简述
给定一棵 \(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）。