自动搬运

查看原文

来自洛谷，原作者为

	lzyqwq 我永远喜欢数据结构。

搬运于2025-08-24 22:50:40，当前版本为作者最后更新于2023-10-27 10:53:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

CNBLOGS

洛谷

• 给出一棵 $n$ 个点的树，边有边权。

• 记 $\text{dist}(u,v)$ 为 $u,v$ 两点简单路径上的边的权值之和。

• 有 $q$ 次询问，每次询问给出 $l,r$，求 $\min\limits_{l\le i<j\le r} \text{dist}(i,j)$。

• $n\le 2\times 10^5$，$q\le 10^6$。

称 $(i,j)\,(i<j)$ 为一个点对，若把 $\text{dist}(i,j)$ 看作改点对的权值，则我们要求解一个二维偏序问题。

现在的问题就是点对太多了，一共有 $\mathcal{O}(n^2)$ 个。不过，真的需要这么多点对吗？比如现在有两个点对 $(x_1,y_1)$ 和 $(x_2,y_2)$ 满足 $x_1\le x_2\le y_2\le y_1$ 且 $\text{dist}(x_1,y_1)\ge \text{dist}(x_2,y_2)$，你发现若查询的区间包含了 $(x_1,y_1)$，就一定包含了 $(x_2,y_2)$，而且 $(x_2,y_2)$ 的权值更小。因此 $(x_1,y_1)$ 这个点对是没有用的。我们称 $\boldsymbol{(x_2,y_2)}$ 支配了 $\boldsymbol{(x_1,y_1)}$。

我们称一个点对为支配点对，当且仅当它不被其他点对支配。

考虑找出一个集合 $T$ 包含所有的支配点对且大小可接受。我们来找一下一个点对成为支配点对的必要条件。

考虑点分治，对于一个支配点对 $(i,j)$，则一定存在一个分治重心 $rt$ 满足 $i,j$ 在 $rt$ 不同儿子的子树中。不妨钦定 $\text{dist}(i,rt)\le \text{dist}(j,rt)$。设 $S$ 表示当前联通块中满足 $\text{dist}(x,rt)\le \text{dist}(j,rt)$ 且 $x\ne j$ 的 $x$ 构成的集合，则 $\boldsymbol{i}$ 一定是 $\boldsymbol{S}$ 中最大的 $\boldsymbol{<j}$ 的数（前驱）或最小的 $\boldsymbol{ >j}$ 的数（后继）。

为什么？考虑反证法，以前驱为例，设 $j$ 的前驱为 $pre$，若 $i<pre$，根据 $S$ 的定义可知 $\text{dist}(i,rt),\text{dist}(pre,rt)\le \text{dist}(j,rt)$。

此时一定满足：

• $\text{dist}(i,pre)\le \text{dist}(i,rt)+\text{dist}(pre,rt)\le \text{dist}(i,rt)+\text{dist}(j,rt)=\text{dist}(i,j)$。

  $\text{dist}(i,pre)\le \text{dist}(i,rt)+\text{dist}(pre,rt)$ 是因为相较于后者前者要减去根到 $\text{LCA}$ 路径的边权和。

• $i<pre<j$。

你发现 $(i,j)$ 被 $(i,pre)$ 支配了。后继的证法类似，此处不再赘述。

考虑这样一个过程，对于每一层点分治，对于每一个点维护集合 $S$，并找到前驱、后继并将该点对加入 $T$。那么任意一个支配点对 $(i,j)$，点分治进行到使得它们在两棵不同子树中的联通块时，因为 $i$ 一定是前驱或后继，那么对于 $j$ 这个点找前驱、后继的时候，就把这个点对找到了。所以这样找到的 $\boldsymbol T$ 集合包含了所有支配点对。

并且，由于点分治只会进行 $\boldsymbol{\mathcal{O}(\log n)}$ 层，每一层每个点带来 $\boldsymbol{\mathcal{O}(1)}$ 个点对，因此找到的总点对数量为 $\boldsymbol{\mathcal{O}(n\log n)}$ 个。

具体地，如何实现这个构造 $T$ 的过程？对于每一个联通块的点分治，将所有点 $u$ 按照编号升序排序。正着反着扫一遍，维护一个随着 $u$ 递增 / 递减，$\text{dist}(u,rt)$ 不降的单调栈。那么对于一个点 $v$，它就是被它出栈的那些点的前驱 / 后继。

我们已经得到了集合 $T$，那么拿 $T$ 中的点对去做二维数点即可。考虑离线 + 倒序扫描 $i$ 保证 $l\le i$，用树状数组维护 $j\le r$ 求前缀最值即可。至于 $\text{dist}(i,j)$，用树剖 + $\text{LCA}$ 求一下即可。

时间复杂度为 $\mathcal{O}(n\log^2 n+q\log n)$，空间复杂度为 $\mathcal{O}(n\log n+q)$。

提交记录 代码