P7880 [Ynoi2006] rldcot

· · 题解

cnblogs

lxl 上课讲的题，来写个题解。

样例很强，赞美 lxl！青蛙，呱 ????。

**[题目传送门](https://www.luogu.com.cn/problem/P7880)** > - 给出一棵 $n$ 个点的有根树。定义 $\text{LCA}(x,y)$ 为 $x,y$ 两点树上的最近公共祖先，$dep_x$ 为 $x$ 到根路径上的边权和。 > > - 有 $m$ 次询问，每次询问给出 $l,r$，求由 $dep_{\text{LCA}(i,j)}\,(l \le i\le j\le r)$ 构成的集合中有几种本质不同的数。 > > - $n\le 10^5$，$m\le 5\times 10^5$。 > > - $500 \,\text{ms}\,/\, 512.00 \,\text{MB}$。 朴素的想法是把所有 $dep_{\text{LCA}(i,j)}$ 找出来然后做 $\text{2 - side}$ 矩形数颜色，但是点对数量为 $\mathcal{O}(n^2)$ 个不可接受。不过所有的点对都有用吗？ 比如有四个点 $a,b,c,d$ 满足 $\text{LCA}(a,b)=\text{LCA}(c,d) = x$ 且 $a< c< d< b$，这时我们发现 $(a,b)$ 这个点对是没用的。因为若一个区间包含了 $(a,b)$ 就一定包含了 $(c,d)$，而我需要统计 $dep_x$，保留 $(c,d)$ 就可以统计到。 这时，我们称 **$\boldsymbol{(c,d)}$ 支配了 $\boldsymbol{(a,b)}$**。称一个点对是支配点对**当且仅当其没有被支配**。容易发现，询问就是查询区间中支配点对的权值构成的集合中有多少种本质不同的数。 考虑找到一个点对集合 $S$ 满足其**包含**所有支配点对且大小可以接受。容易发现我们此时需要寻找一个点对成为支配点对的**必要**条件。 考虑在 $\text{LCA}$ 处统计。即，对于 $x\in[1,n]$，当一个点对 $(u,v)$ 满足 $\text{LCA}(u,v)=x$ 时，我们来寻找它成为支配点对的必要条件。 首先，这两个点一定在 $x$ 的不同子树中。记 $T$ 表示 $x$ 的子树中 $u$ 所在子树外的点构成的集合，则 **$\boldsymbol{v}$ 一定是 $\boldsymbol{T}$ 中最大的小于 $\boldsymbol{u}$ 的点（前驱 $\boldsymbol{pre}$）或最小的大于 $\boldsymbol{u}$ 的点（后继 $\boldsymbol{nxt}$）**。 以前驱为例，考虑反证，即当 $v\ne pre$ 时，我们先理出已知条件： - $v<pre<u

我们发现此时 (pre,u) 支配了 (v,u)。后继证法类似，此处不再赘述。

考虑一个树上启发式合并的过程，维护一个 std::set 表示当前子树及之前子树中所有点构成的点集，每次继承重儿子，遍历轻儿子时在 std::set 中找前驱、后继，并将该子树合并进 std::set。

那么对于一个支配点对 (u,v)，其一定满足上述条件，在启发式合并 \text{LCA}(u,v) 时，u,v 一定在不同的子树中（或位于根）。不妨钦定 v 所在子树更靠后，那么在处理 v 所在子树之前，u 已经被合并进了 std::set 中，且 u 一定是 v 的前驱 / 后继。那么对于 v 找前驱 / 后继的时候就找到了这个点对。

需要说清楚的是，对于 v 而言，此时的 std::set 是 \boldsymbol{T} 的一个子集。不过一个点在 T 中成为 v 的前驱 / 后继的必要条件是它在这个自己中成为 v 的前驱 / 后继，所以可以在子集中找前驱 / 后继。

因此 T 集合包含了所有的支配点对。并且，根据树上启发式合并的性质，一个点只会被遍历 \boldsymbol{\mathcal{O}(\log n)} 次，一次遍历找的是前驱 / 后继，会带来 \boldsymbol{\mathcal{O}(1)} 个点对，因此 \boldsymbol{|T|=\mathcal{O}(n\log n)}，可以接受。

找出这些点对后，就可以进行 \text{2 - side} 矩形数颜色了。考虑扫描线，从右往左扫。设当前扫到 x，维护一个数组 pos 表示每种颜色在左点 \ge x 的点对构成的点集中，右点的最小值。区间查询 [l,r] 等价于查询在左点 \ge l 的点对构成的点集中，有多少种颜色的 pos 值 \le r，因此再对 pos 维护一个权值树状数组即可。

综上本做法时间复杂度为 \mathcal{O}(n\log ^2 n+q\log n)，空间复杂度为 \mathcal{O}(n\log n+q)。

提交记录（\color{white}\colorbox{Limegreen} {\bf Accepted 100} \boldsymbol{404\,\bold{ms}\,/\, 57.33\,\bold{MB}}） 代码