CF364E Empty Rectangles

题意：给出一个 的 矩阵，求有多少个子矩阵含有恰好 个 。

，，时限 。

---

考虑分治，轮换切割整个矩阵。

每次只需要考虑跨越分割线的子矩阵。

枚举子矩阵的上下两个边界，如图（红色是上下边界）

然后枚举左侧有多少个 ，右侧也随之确定。

设 为左侧包含 个 最近延伸的距离。特殊地，若得不到 个，则值为横向距离 。

类似。

则矩形个数为 考虑如何求出 。

固定上边界，将下边界逐渐下移。

每移动一格，则会加入一行 ，只需处理前 个的影响。归并即可。

需要预处理每个位置左边的第一个 和右边的第一个 。

分析复杂度时不妨设 ，一次分割的复杂度为 ，由于分割出的区域近似于正方形，割线长度的平方近似于面积。复杂度为 。