自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 22:59:18，当前版本为作者最后更新于2024-05-09 23:41:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Preface

deleted。

Solution

$\mathcal O((n + m)\log n)$

不失一般性，$k = 1$，否则我们把点按照 $\bmod k$ 同余分成若干类，每一类是一个独立的问题。另注：我们需要忽视 $(u - v) \bmod k \neq 0$ 的所有边 $(u, v)$。

解决 $s = 1$。我们发现若初始权值为 $[1, i]$ 的所有点的最终权值都是 $1$，这要求每个初始权值为 $[1, i)$ 的点 $x$ 都与至少一个初始权值在 $(x, i]$ 内的点相连。我们显然可以 $\mathcal O(n)$ 解决。

解决 $s$ 是一般值的情况。考虑 $[l, r]$ 最终全是 $s$ 的充要条件是

• $[l, r]$ 联通；
• 每个 $(s, r)$ 与 $(s, r]$ 里更大的点直接有边；
• 每个 $(l, s)$ 与 $[l, s)$ 里更小的点直接有边。

忽视第一个条件，第二个条件我们对每个 $r$ 找到最大的 $s + 1$，这可以从小到大扫描 $r$，不断加入 $x$ 的贡献，用并查集维护连续段解决；第三个条件同理。

接下来我们对每个 $s$ 找到了如果第一个条件成立下的 $L = l_{\min}$ 和 $R = r_{\max}$，于是这些点被划分成了三个部分：$[L, s) [s, s] (s, R]$。

显然，如果 $[s, s]$ 与 $[L, s) (s, R]$ 中其中 $0$ 或 $2$ 个部分联通，我们可以简单计算最终连通块的大小；否则我们不妨设 $[s, s]$ 与 $[L, s)$ 联通而不与 $(s, R]$ 联通，但我们注意到这个时候最终连通块不一定仅仅是 $[L, s]$，也有可能是 $[L, s)$ 与 $(s, R]$ 内有边导致最终的最大连通块为 $[L, R]$。判断两个区间内的点是否有边可以离线后二维偏序解决。

于是时间复杂度为 $\mathcal O((n + m)\log n)$。

$\mathcal O(n + m)$

我们线性计算上面的每个部分。

• 对于每个 $i$ 计算最大的 $R_i$ 满足 $[i, R_i)$ 的每个点 $x$ 都与 $(x, R_i]$ 间的一个点相连，对称同理

断言：$R_i = R_{i+1}$ 或 $R_i = i$，证明显然：若无 $R_i \leq R_{i+1}$ 则有矛盾；若 $R_i \in (i, R_{i+1})$ 依然有矛盾。那么枚举 $i$ 的出边即可。

• 对于若干个 $i$，判断 $[L_{i-1}, i)$ 与 $(i, R_{i+1}]$ 之间是否有边

对于一条边 $u, v (u < v)$，能够让 $L_{i-1} \leq u \leq i - 1$，$i + 1 \leq v \leq R_{i+1}$ 的点合法。由于 $L$，$R$ 的单调性，这可以转化为有某个 $[l, r]$ 使得 $i \in [l, r]$ 是合法的。这可以差分预处理。

于是时间复杂度为 $\mathcal O(n + m)$。

另一个线性做法：欢迎报名月赛讲评。