wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数据结构

线段树

线段树单点修改

线段树区间修改

动态开点线段树

线段树的合并（一）

线段树的分裂

线段树的合并（二）

可持久化线段树

树链剖分

平衡树

FHQ-Treap

珂朵莉树

分块

位分块

根号分治

虚树

[[ item.c ]]

线段树的合并（二）

本文选取线段树合并（分裂）中，一些典型的例子
## [POI2011] ROT-Tree Rotations
**[[POI 2011] ROT-Tree Rotations](https://www.luogu.com.cn/problem/P3521)**
给定一个二叉树，根不是叶子节点，保证每一个非叶子节点有`2`个儿子
每一个叶子有一个权值，一共有$$n$$个叶子，保证所有叶子的权值构成$$1 \sim n$$的排列
可以任意交换一个点的左右子树，求先序遍历遇到的叶子节点的权值，构成的序列
它的最少逆序对数是多少？

**算法分析**
![](/media/content_img/luoguP3521.png)

## CF208E Blood Cousins
**[CF208E Blood Cousins](https://www.luogu.com.cn/problem/CF208E)**
给定一个森林，若干次询问，每次给出一个点，求它的某个祖先的子树上，与它深度相同的节点的个数

**算法分析**
离线，把所有询问挂载到对应的祖先节点上（树上倍增查祖先）
然后`dfs`执行线段树合并，线段树是按`dep 深度`作为权值的

比如`dfs(u)`，合并完子树之后，`tr.change(root[u], dep[u], +1)`这样

> 为了省空间，可以“阅后即焚”

考虑`dfs(u)`，然后`root[u] = merge(root[u], root[v])`
接着`tr.change(root[u], dep[u], +1)`，接着就可以立马结算了

遍历`u`身上挂载的询问$$v_i$$，在`root[u]`中查询`dep[vi]`这个叶子节点的值
作为答案，存入`ans[queryID]`中

> 坑点，问题给定的是森林，每一棵树的`root`单独计算

### 卡常版，怎么找 K 级祖先
**[[Cnoi2019] 雪松果树](https://www.luogu.com.cn/problem/P5384)**
可以考虑用**路径栈**
```bash
auto dfs = [&](auto &dfs, int u, int fa, int d) -> void {
	dep[u] = d;
	stk.push_back(u);
	
	栈中所有的元素都是 u 的祖先
	p 级祖先就是 stk[stk.size() - 1 - p]
	
	for (auto v : g[u]) {
		if (v != fa) dfs(dfs, v, u);
	}
	
	stk.pop_back();
};
```

> 对每个询问**离线**之后，考虑`u`上挂载的询问`(D, qid)`
实际上就是在`u`的子树中，深度为`D`的节点有多少个？
这就是一个**二维数点**问题，在横坐标** dfs 序**`[in(u), out(u)]`区间内，纵坐标是`D`的点有多少个？

这种特殊的二维数点，可以直接用二分查找来求解
直接对每一个深度`D`**开一个桶**，`nodes[D]`
`dfs(u)`到`u`的时候，`nodes[ dep[u] ].push_back( u 的 dfs 序 in[u] )`

查询的时候，对于询问`(u, D, qid)`，实际上就是在`nodes[D]`中看`(in[u], out[u])`有多少个元素
`itr = upper_bound(out(u)), itl = lower_bound(in(u))`
直接`itr - itl`就是`u`的子树中，深度为`D`的点有多少个

## Dominant Indices
**[F. Dominant Indices](https://codeforces.com/problemset/problem/1009/F)**
给定一棵以`1`为根的树，$$d(u, x)$$为`u`子树（包括`u`）到`u`距离为`x`的节点个数
对于每个点，求一个最小的`k`，使得`d(u, k)`最大

**算法分析**
根据绝对深度`dep[u]`，建权值线段树，考虑线段树合并，`merge(root[u], root[v])`
`dfs(u)`的时候，`change(root[u], dep[u], +1)`

然后在`root[u]`上查询即可，线段树维护信息，`(Info a) + (Info b)`
优先考虑`return info.cnt 较大`的那个节点，如果`info`相同，返回`info.dep`较小的节点

询问的时候，直接查`ret = tr.rangeQuery(root[u], 1, tr.n)`这个根节点信息即可
返回`ret - dep[u]`就是`u`的答案

## Tree Requests
**[D. Tree Requests](https://codeforces.com/contest/570/problem/D)**
给定一个有根树，每个点上有一个小写字母，每次询问给定`a, d`
查询`a`为根的子树中（包括`a`），深度为`d`的所有节点上的字母，重新排列后能不能构成回文串

**算法分析**
离线所有询问，挂载到节点上

仍然考虑线段树合并，开权值线段树，权值（叶节点）是`dep`
每个叶子节点`D`维护两个信息，`cnt`表示这个深度`D`有多少个字符
另一方面，需要维护一个`mask`，`26`位的二进制数

当`dfs(u)`的时候，合并所有子树，`root[u] = merge(root[u], root[v])`
单点修改`tr.change(root[u], dep[u], cnt 对应 +1)`
另外，假设说`char[u] = ch, sta ^= (1 << ch)`，同时，`tr.change(root[u], dep[u], 节点对应的 mask ^= sta)`

线段树节点更新，`a.cnt += b.cnt,    a.mask ^= b.mask`，这样就维护好了

接下来查询，假设说要查询`深度 D`，令`ret = tr.rangeQuery(root[u], D)`
当`cnt % 2 == 0`是偶数的时候，`popcnt(ret.mask) 必须是 0`
当`cnt % 2 == 1`的时候，要求`popcnt(ret.mask) <= 1`即可，其他情况都不满足

## Codeforces Round 151 (Div. 2)
### E
**[E. Blood Cousins Return](https://codeforces.com/contest/246/problem/E)**
给定一个森林，每个点上都有一个字符串。每次询问，给定一个点`u`
求 k-son 有多少个不同的字符串

**算法分析**
离线，把询问挂载到点上，对每个点，仅考虑它的子树
回答子树中，所有深度为`D = dep[u] + K`的点，有多少种不同的名字（字符串）

DSU-On-Tree 可以做，线段树合并也可以做

**每一个点，对深度`dep`开权值线段树**，深度为`dep`的叶子节点，用一个`set<int> S`来维护信息

1）这个问题中，所有的合并，查询，结算，都是在叶子节点进行，所以不需要`pull`方法
否则，每次拷贝，针对节点，都必须整个`set`拿去拷贝

2）因此，`operator+`方法也不需要了，而是自己写一个`pointQuery(int root, int pos)`方法

3）注意，线段树合并的时候，是合并两个`set`，用启发式合并
传统的合并方式，`t[p].info = op( t[p].info, t[q].info )`，在`set`合并上，会发生拷贝
`set`的`size`一旦变得足够大，复杂度就退化成$$O(n^2)$$

这里可以优化性能
```bash
struct MergeOp {
    void operator() (Info &a, Info &b) const {
        if (a.S.size() < b.S.size()) swap(a, b);
        for (auto y : b.S) a.S.emplace(y);
    };
};
调用的时候
template<class F = MergeOp>
int merge(int p, int q, int l, int r, F &&op = F()) {
	if (!p or !q) return p | q;
	if (l >= r) {
		op(t[p].info, t[q].info);
		recycle(q);
		return p;
	}
}
```

4）查询，也一定要避免返回整个`set`，选择`return t[p].info.S.size()`，不能把整个`set`返回
```bash
int pointQuery(int p, int l, int r, int pos) {
	if (l >= r) {
		return t[p].info.S.size();
	} 
	int mid = (l + r) >> 1;
	if (pos <= mid) return pointQuery(t[p].ls, l, mid, pos);
	else return pointQuery(t[p].rs, mid + 1, r, pos);
}
int pointQuery(int p, int pos) {
	return pointQuery(p, 1, n, pos);
}
```

只需要注意上述坑点，线段树合并就非常套路了
1）`dfs(u)`的时候，合并所有儿子`root[u] = tr.merge(root[u], root[v])`
2）单点修改，`tr.change(root[u], dep[u], {a[u]})`
3）对于`u`上挂载的询问`K`，对应绝对深度`D = dep[u] + K`，在`root[u]`线段树中查单点

> 坑点

值得注意的是，如果`operator+`方法或者`pull`方法有变更
比如特殊结构的线段树，非叶节点，仅仅起到一个导航作用，不需要维护任何信息
那么`operator+`可能要留空

而`rangeQuery`中，我们写`return rangeQuery(t[p].ls...) + rangeQuery(t[p].rs...)`也可能会失效
这个时候，要自己额外写一个`pointQuery(int root, int pos)`查询叶节点的方法，这并不难

## 线段树合并优化 dp 转移
### 树上 LIS
**[[FJOI2018] 领导集团问题](https://www.luogu.com.cn/problem/P4577)**
给定一棵树，假设说你在树上选了两个点$$(u, v)$$，如果`u 是 v 的祖先`
必须保证权值$$w_v \geqslant w_u$$，如果你选点的话，越靠近根，点的权值必须越小
问最多能够在树上选几个点

**算法分析**
![](/media/content_img/P4577-01.png)
![](/media/content_img/P4577-02.png)
![](/media/content_img/P4577-03.png)

**算法实现**
```bash
void solve(int cas) {
    int n;
    cin >> n;
    vector<i64> w(n+1, 0), rm;
    for (int i = 1; i <= n; i++) cin >> w[i], rm.emplace_back(w[i]);

ranges::sort(rm);
    rm.erase(ranges::unique(rm).begin(), rm.end());
    for (int i = 1; i <= n; i++) w[i] = ranges::lower_bound(rm, w[i]) - rm.begin() + 1;

vector<vector<int> > g(n+1);
    for (int x = 2; x <= n; x++) {
        int y;
        cin >> y;
        g[y].emplace_back(x), g[x].emplace_back(y);
    }

DynamicLazySegtree<Info, Tag> tr(n);
    vector<int> root(n+5, 0);

auto dfs = [&](auto &dfs, int u, int fa) -> void {
        for (auto v : g[u]) {
            if (v == fa) continue;
            dfs(dfs, v, u);
        }

i64 add = 1;
        for (auto v : g[u]) {
            if (v == fa) continue;
            add += tr.rangeQuery(root[v], w[u], tr.n).dpv;
        }

for (auto v : g[u]) {
            if (v == fa) continue;
            root[u] = tr.Merge(root[u], root[v], 1, tr.n);
        }

tr.change(root[u], w[u], Info{add});
    };
    dfs(dfs, 1, 0);

i64 ans = 0;
    for (int x = 1; x <= tr.n; x++) chmax(ans, tr.pointQuery(root[1], x).dpv);

cout << ans << "\n";
}
// 线段树合并代码
template<class Info, class Tag>
class DynamicLazySegtree {
    int Merge(int p, int q, int l, int r, i64 suf1 = 0, i64 suf2 = 0) {
        if (!p and !q) return 0;
        if (!q) {
            apply(p, {suf2});
            return p;
        }
        if (!p) {
            apply(q, {suf1});
            return q;
        }

if (l >= r) {
            i64 dpv1 = t[p].info.dpv + max(suf2, t[q].info.dpv);
            i64 dpv2 = t[q].info.dpv + max(suf1, t[p].info.dpv);

t[p].info = Info{ max(dpv1, dpv2) };
            recycle(q);
            return p;
        }

int mid = (l + r) >> 1;
        push(p), push(q);

i64 pdpv = t[ t[p].rs ].info.dpv;
        i64 qdpv = t[ t[q].rs ].info.dpv;

t[p].ls = Merge(t[p].ls, t[q].ls, l, mid, max(suf1, pdpv), max(suf2, qdpv));
        t[p].rs = Merge(t[p].rs, t[q].rs, mid+1, r, suf1, suf2);

pull(p);
        recycle(q);
        return p;
    }
}
```
### NOI2020 命运
**[[NOI2020] 命运](https://www.luogu.com.cn/problem/P6773)**
给定`n`个点的树，给定`m`个点对，每个点对$$(x, y)$$，`x`是`y`的祖先
树上的每条边都要图上白色或者是黑色，完全由你决定
但是你必须保证，经过每个点对的路径中，至少有一条黑色的边存在
求涂色的方案数，对`998244353 取 mod`

**算法分析**
![](/media/content_img/NOI2020fate01.png)
![](/media/content_img/NOI2020fate02.png)
![](/media/content_img/NOI2020fate03.png)
![](/media/content_img/NOI2020fate04.png)
**算法实现**
```bash
// 线段树合并部分
int Merge(int p, int q, int l, int r, const mint S, const int lim, mint prep = 0, mint preq = 0) {
    if (!p and !q) return 0;
    if (l > lim) return 0;
    if (!q) {
        mint mul = S + preq;
        apply(p, Tag{mul});
        return p;
    }
    if (!p) {
        mint mul = prep;
        apply(q, Tag{mul});
        return q;
    }
    if (l >= r) {
        auto dpvp = t[p].info.dpv;
        auto dpvq = t[q].info.dpv;
        mint dpv = dpvp * (S + preq + dpvq) + dpvq * prep;
        t[p].info.dpv = dpv;
        return p;
    }
    int mid = (l + r) >> 1;
    push(p, l, r), push(q, l, r);

mint pdpv = t[t[p].ls].info.dpv;
    mint qdpv = t[t[q].ls].info.dpv;

t[p].ls = Merge(t[p].ls, t[q].ls, l, mid, S, lim, prep, preq);
    t[p].rs = Merge(t[p].rs, t[q].rs, mid+1, r, S, lim, prep + pdpv, preq + qdpv);

pull(p);

// 回收 q
    recycle(q);
    return p;
}
// 主代码
auto dfs = [&](auto &dfs, int u, int fa) -> void {
    tr.change(root[u], maxs[u], {1});

for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(dfs, v, u);
    }

for (auto v : g[u]) {
        if (v == fa) continue;
        mint S = tr.rangeQuery(root[v], 0, dep[u]).dpv;
        root[u] = tr.Merge(root[u], root[v], 0, n, S, dep[u]);
    }
};
dfs(dfs, 1, 0);
```
## 线段树的分裂
### Educational Codeforces Round 35
**[G. Mass Change Queries](https://codeforces.com/contest/911/problem/G)**
给定一个长度为`n`的整数序列`a`，需要执行`q`次操作，每次操作给定`l, r, x, y`
表示对每个$$l \leqslant i \leqslant r$$，如果$$a_i = x$$，那么令$$a_i = y$$

**算法分析**
注意到值域最多才到`100`，可以对每个值开一棵线段树，然后用线段树的合并和分裂

**初始化**
对`for x = a[i]`，在`root[x]`上执行`tr.change(root[x], i, {1})`

**修改操作**
`l r x y`
1）先在`root[x]`上把`[l, r]`区间给剥离`split(l, r)`出来，放到一棵新树`temp`上
2）然后把`temp`合并到`root[y]`上

**输出答案**
对没一棵树，`root[x]`，`dfs`这棵树，如果走到叶子节点`l >= r`，那么说明`l`这个位置，确实有值`x`
令`ans[l] = x`即可

看完文章有啥想法

算法小站

wiki 主题

数据结构

线段树的合并（二）

目录