线段树合并

by TheBigYellowDuck

背景

封闭的第一次模拟赛遇到了这个科技，因为完全不会喜提 $20 \text{pts}$。

事后发现这个东西很好玩，赶紧学了一下。

前置知识

线段树合并是将两棵值域相同的权值线段树合并的算法，一般用来合并动态开点权值线段树。

普通权值线段树也可以合并，但是意义不大。

其本质是对应位置相加，虽然看起来很暴力，但一次合并的复杂度是优秀的 $\mathcal{O}(\log{n})$。

实现上跟正常动态开点权值线段树几乎一致，差别只在合并上。

实现参考：

int merge(int u, int v, int l, int r) {
    if (u == 0 || v == 0)
        return u + v;
    if (l == r) {
        sum[u] += sum[v];
        return u;
    }
    int mid = (l + r) >> 1;
    ls[u] = merge(ls[u], ls[v], l, mid);
    rs[u] = merge(rs[u], rs[v], mid + 1, r);
    return pushup(u), u;
}

Problem 1

有 $n$ 个数，第 $i$ 个数的颜色为 $c_i$。初始时每个数所属集合只包含自己。进行 $q$ 次操作：

• 合并 $a$ 和 $b$ 所在集合。

• 查询 $x$ 所在集合中颜色为 $y$ 的数的个数。

数据范围：$c_i\leq n,q\leq 2\times10^5$。

Sol

线段树合并模板。

操作一容易想到并查集，操作二是权值线段树上单点查询问题。

于是用并查集维护集合，合并集合的同时把两个集合的权值线段树合并。在权值线段树上单点查询即可。注意并查集的合并方向要和权值线段树保持一致。

时间复杂度 $\mathcal{O}(n\log{n}+q\log{n})$。

题目来源： ABC183F Confluence

Problem 2

给定一张 $n$ 个点 $m$ 条边的无向图，每个点有权值 $v_i$。进行 $q$ 次操作：

• 在点 $x$ 和点 $y$ 之间连边。

• 查询点 $x$ 所在连通块内权值第 $k$ 小的点的编号。不存在输出 $-1$。

数据范围： $v_i\leq m\leq n\leq 10^5$，$q\leq 3\times 10^5$。

Sol

换汤不换药。

维护连通块还是在维护集合。查询可以在权值线段树上完成，直接无脑线段树合并。

和上一题的写法几乎一样，只是要查询的东西不同。

时间复杂度 $\mathcal{O}(n\log{n}+q\log{n})$。

题目来源： HNOI2012 永无乡

Problem 3

给定一棵根为 $1$ 的树，节点 $i$ 的权值为 $p_i$。对于所有 $1\leq i\leq n$ 求节点 $i$ 的子树中权值大于 $p_i$ 的节点个数。

数据范围： $n\leq 10^5$，$p_i\leq 10^9$。

Sol

先离散化。

注意到节点 $i$ 的答案其实就是在权值线段树上区间 $[p_i+1,n]$ 的和。考虑在每一个叶子节点建权值线段树，不断向上合并，合并到节点 $i$ 时直接可以求出 $i$ 的答案。

时间复杂度 $\mathcal{O}(n\log n)$。

题目来源：USACO2017 Promotion Counting

Problem 4

村落里一共有 $n$ 座房屋，形成一个树。发放 $m$ 次救济粮，每次选择两个房屋 $x, y$，然后对于 $x$ 到 $y$ 的路径上每座房子里发放一袋 $z$ 类型的救济粮。

当所有的救济粮发放完毕后，求每座房子里存放的最多的救济粮类型。

数据范围：$n,m,z\leq 10^5$。

Sol

先通过树上差分把链上的操作转化为单点操作。

权值线段树记录出现次数的最大值及其类型，从叶子节点向上合并即可。

时间复杂度 $\mathcal{O}(n\log n+m\log n)$。

题目来源：P4556 雨天的尾巴

Problem 5

游戏的地图为一棵 $n$ 个节点的树，现在有 $m$ 个玩家，第 $i$ 个玩家的起点为 $s_i$ 终点为 $t_i$。所有玩家在第 $0$ 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家退出游戏。

每个节点上都存在一个观察员。在节点 $j$ 的观察员会在第 $w_j$ 秒观察玩家，玩家能被观察员观察到当且仅当玩家在第 $w_j$ 秒也正好到达了节点 $j$。求每个观察员会观察到的人数。

数据范围：$n,m\leq 3\times 10^5$。

Sol

考虑统计每条路径对观察员做出的贡献。

对于路径 $(s,t)$，设 $l=\operatorname{lca}(s,t)$，把路径拆成上行路段 $(s,l)$ 和下行路段 $(l,t)$ 两段。不妨认为 $l$ 在上行路段上。

设 $dep_u$ 为节点 $u$ 的深度，观察员位置为 $k$，分类讨论：

• 若 $k$ 在路径 $(s,l)$ 上，则想要做出贡献需要满足

$dep_s=dep_k+w_k$

• 若 $k$ 在路径 $(l,t)$ 上，则想要做出贡献需要满足

$dep_s-dep_l+dep_k-dep_l=w_k$

$dep_k-w_k=2\times dep_l-dep_s$

考虑在每个点上开一棵权值线段树。对于第一个式子，我们可以在路径 $(s,l)$ 上的每一个点的权值线段树上标记 $dep_s$，则对于观察员 $k$ 只需要查询权值线段树上单点 $dep_k+w_k$ 的值，就可以知道经过 $k$ 的上行路段数量。

进一步考虑，在一条路径上全部标记 $dep_s$ 可以通过树上差分转化为在 $s$ 的权值线段树上标记 $dep_s$ 而在 $fa_l$ 的权值线段树上撤销，从下往上进行线段树合并，就可以得到答案。

对于第二个式子同理。在 $t$ 的权值线段树上标记 $2\times dep_l-dep_s$ 并在 $l$ 的权值线段树上撤销，从下往上合并答案，对于观察员 $k$ 只需要查询权值线段树上单点 $dep_k-w_k$ 的值，就可以知道经过 $k$ 的下行路段数量。

注意这里 $fa_l$ 和 $l$ 的区别是因为我们把 $l$ 归入了上行路段，其实反过来也是一样的。

减法有可能出负数，值域设为 $[-n,n]$ 即可。

时间复杂度 $\mathcal{O}(n\log n+m\log n)$。

题目来源：NOIP2016 提高组 天天爱跑步

Problem 6

给定一颗有 $n$ 个叶节点的二叉树。每个叶节点都有一个权值 $p_i$，所有叶节点的权值构成一个 $1 \sim n$ 的排列。

对于这棵二叉树的任何一个结点，保证其要么是叶节点，要么左右两个孩子都存在。
现在你可以任选一些节点，交换这些节点的左右子树。

在最终的树上，按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 $n$ 的排列，你需要最小化这个排列的逆序对数。

数据范围：$n\leq 2\times 10^5$。

Sol

考虑一个节点的子树的先序遍历序列中逆序对的来源有三种：

• 左子树内部的逆序对

• 右子树内部的逆序对

• 横跨左右子树产生的逆序对。

注意到交换子树的操作只会影响第三种逆序对的数量，考虑对交换和不交换分别计数。

设当前要合并的左右子树的根分别为 $u$ 和 $v$。若不交换左右子树，产生的逆序对数量为

$\sum rs(u)\times \sum ls(v)$

若交换左右子树，产生的逆序对数量为

$\sum ls(u)\times \sum rs(v)$

递归的时候对每一个节点的两式取最小值即可。

读入是一个递归的形式，所以可以一边读入一边做，正好也满足从叶子向上合并的顺序。

时间复杂度 $\mathcal{O}(n\log n)$。

题目来源：P3521 POI2011 Tree Rotations

Problem 7

P3201 HNOI2009 梦幻布丁

Problem 8

CF600E Lomsat gelral

Problem 9

给定 $n$ 个点的有根树，每个点权值为 $w_i$。对于每个点 $i$， 求以 $i$ 为根的子树中权值集合的 $\text{mex}$，即集合中未出现的最小正整数。

数据范围：$n,w_i\leq 10^5$。

Sol

只要知道如何用权值线段树处理 $\text{mex}$，就可以用线段树合并。

设当前递归到的权值线段树的根为 $u$，值域区间为 $[l,r]$，考虑如下情况：

• 若 $u=0$，说明已经递归到了边界，答案为 $l$。

• 若子树和等于值域区间长度，说明子树已经被填满，答案为 $r+1$。

• 若左子树的答案小等于于 $\left\lfloor\dfrac{l+r}{2}\right\rfloor$，说明左子树还未填满，答案为左子树的答案。

• 否则，左子树填满，答案为右子树的答案。

int query(int rt, int l, int r) {
    if (!rt) return l;
    if (sum[rt] == r - l + 1) return r + 1;
    int mid = (l + r) >> 1;
    int res = query(ls[rt], l, mid);
    if (res <= mid) return res;
    return query(rs[rt], mid + 1, r);
}

用处理树形问题的常规手段，从叶子向上进行线段树合并即可。

时间复杂度 $\mathcal{O}(n\log n)$。

题目来源：？