P10573 Solution
irris
·
·
题解
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 的充要条件是
-
- 每个 (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)。
另一个线性做法：欢迎报名月赛讲评。