P10573 题解

· · 题解

先把图按照对 k 的余数拆分开来，显然，对 k 余数不同的点相互之间不可能有贡献。

把拆分后的图的点权重新标为从 1 开始的连续的一段，之后讨论在这样一张图中做 k=1 的情况。

假设你有了一个 s，讨论如何计算答案。注意到每一个点的点权都是不重的，所以将一个点的点权转化为另一个点的点权代表着有一个值的消失。而所有满足 a_x=s 的点又不能进行修改，所以你不会作出类似于把 s+k 变为 s+k+1 这样的事，因为 s+k 这个值补不回来了，这些数降不回去。

所以，每个数都只会接近 s 地改变，若一个值得区间 [l,r] 最终都变成了 s，那么一定有：

考虑处理上面的三个部分。

第二和第三部分类似，对每一个点维护它能连到的距离它最小的比它大和比它小的点。

以第二部分为例。可以发现这个玩意真是单单又调调，每一个 s 对应的右端点单调递增（因为限制严格减少）。相应的，我们倒序枚举 s，这个东西就会递减。倒序去计算它，如果当前的没有向比它大的点连边，或是连到的点超出了上一个点的右端点，把 r 置为 s，一直处理下去即可。

最后再判断第一个条件，检查 [l_s,s-1],s,[s+1,r_s] 相互之间是否有边即可。

最后的复杂度就是 O(n+m)。