CF763E Timofey and our friends animals

MiniLong · 2024-07-03 16:15:09 · 题解

要啥莫队啊。

跟 CF811E 类似，由于一个点只会连与它距离不超过 k 的点，所以如果一个联通块最左、最右是 l,r，并且 [l-k,l-1],[r+1,r+k] 都没有跟这个联通块相连的，那么再往外就不可能有与它相连的了。所以也考虑线段树维护 [l,r]，记录 [l,r] 的联通块个数，并且维护 [l,l+k-1],[r-k+1,r] 每个点所在的联通块。合并直接开个 4k 大小空间的并查集合并这些点就好了，注意区间小的时候还要更新左边和右边的 k 个点。复杂度 \Theta(nk^2 \log n)。