题解：P14532 [RMI 2018] 颜色 / Colors

__O_v_O__ · 2026-03-10 16:11:49 · 题解

显然如果存在 a_i<b_i 那么不行，所以假设所有 a_i\ge b_i。

考虑我们的操作一定是把一个点的点权挪到另一个点上去。设当前需要使一个点的点权变成 k，显然需要从某些 a_i=k 的点传过来。注意到不是所有 a_i=k 的点都能传过来，必须要满足条件：存在一条传过来的路径，满足每个路径上的点 x 都有 b_x\le k\le a_x（如果 k<b_x 那么该点无法再回到 b_x；如果 k>a_x 那么 k 无法传到该点）。那么对于一个 k，只有一部分的点和边能用。如果在新图上某个需要变成 k 的点还和一个 a_i=k 的点连通，那么它就可以满足条件。

我们可以证明，如果对于每个点都满足上面的条件，那么一定可以完成题目中的任务。必要性显然，充分性考虑按 k 从大到小来做操作，前面的操作是一定不会影响后面的过程的。

那么对于每条边 (u,v)，它只在 k\in[b_u,a_u]\cap[b_v,a_v] 时存在。我们把 k 看成时间，那么在 k 时间点时，整张图会被划分为若干个连通块，枚举所有 a_i=k 的节点，标记它们所在的连通块，再枚举所有 b_i=k 的节点，如果存在一点所在的连通块没有标记，那么答案就是不行。如果对于所有 k 都满足，那么答案是可以。

并查集维护连通性，每条边只能在一个时间区间中存在，线段树分治即可。

代码是比较板的线段树分治，这里就不给了。