题解：AT_arc219_e [ARC219E] Equal Distribution

· · 题解

考虑在一维的情况上怎么做，就是一个 2n 的环选 n 个位置使得恰好两个部分都包含了 n/2 个关键点。

维护滑动窗口，每次窗口右移一位变化量只会是 0,\pm 1，所以肯定存在一个时刻恰好包含 n/2 个关键点。

而我们在二维上想办法把他也变成一维的环状即可，最简单的就是网格图上找一条哈密顿回路。

长宽都是偶数，一个显然的构造是：

即可把二维问题转化为一维问题。此时任意选一个区间剥掉，选出来的区间和剩下的区域一定在原来的网格图上形成连通块。然后维护一个滑动窗口内部的关键点数量即可。

https://atcoder.jp/contests/arc219/submissions/75706416