K 分块是什么？

litjohn · 2026-05-08 23:47:19 · 题解

题解区莫名都使用了线段树优化建图，只有一个人是并查集优化建图，复杂度普遍是 log 平方。

但事实上本题可以容易的做到单 log（二分的 log）。就是使用标题中的科技：K 分块。

其实根本不算科技。非常简单的小技巧。

想必各位还记得 ABC456F 吧？那个题需要维护滑动窗口中不可差分的值（区间 (\min, +) 矩阵积）。

可以使用非删尺取去掉线段树的 log。具体见下文：

https://litjohn.pages.dev/posts/2-pointers-with-no-deletion/

另一种做法就是 K 分块：把序列按照 k 的长度分块，此时发现每个长度为 k 的滑动窗口都恰好覆盖一个块的前缀和一个块的后缀。于是我们维护每个块的前后缀信息，查询时拼起来即可。

看上去没啥用，完全比不上非删尺取。但是在本题中作用就体现出来了：K 分块能够优化建图。

具体的，对于每个块，我们设置一系列节点代表这个块长度为 x 的前/后缀（x \in [1, k]）中是否选了点。

然后就是比较套路的建图和 2-SAT 了。题解区已经讲的很明白。

放一下我的提交记录。