题解：P13647 [NOISG 2016] Fabric

· · 题解

序

NOIP 前的信心赛 T4 搬了这道题，和两个月前的 AT_abc420_f 一模一样很难崩，更难崩的是我打了那场却没有补。

这道题可以单调栈或笛卡尔树做到 O(nm)，赛时写的是单调栈 （为什么我永远想不到笛卡尔树）。线性做法比较套路，这里介绍一种 O(nm \log nm) 却更加强大的做法，几乎适用于所有子矩形计数问题。

题意

给定一个 n \times m 的 01 矩阵 M，求出有多少个面积 \ge k 的子矩阵满足子矩阵内没有 1。

## 题解 对于任何一个合法的矩形 $(x1, y1, x2, y2) = [x1,x2] \times [y1, y2]$，其中 $[x1, x2]$ 和 $[y1, y2]$ 分别是行和列上的一个区间，考虑对矩阵分治。每次选择长的一边割开，然后计算经过分割线的合法矩形数量。 不妨假设我们横着将矩形分开，沿行中点 $mid = \lfloor \frac{x_1+x_2}{2}\rfloor$ 分成上下两块，固定列区间： 对每列 $y$，我们定义： - $U[y]$：从中线向上能延伸的最远行。 - $D[y]$：从中线向下能延伸的最远行。 对列区间 $[c_1,c_2]$，最大可形成的跨线矩形为 $$[x_{\text{top}},x_{\text{bottom}}]\times[c_1,c_2],\quad x_{\text{top}} = \max(U[c_1..c_2]),\; x_{\text{bottom}} = \min(D[c_1..c_2]) $$ 我们需要统计所有 $$[x_{\text{top}},x_{\text{bottom}}] \times [c_1, c_2]$$ 跨过分割线，且面积 $\ge k$ 的子矩形。 这个东西形式化后是给定线段 $[l, r]$，其中 $mid$ 将线段划分为 $[l, mid],[mid, r]$，求在这两部分分别选择两个点连接为线段，线段长度 $\ge \left\lceil \frac{k}{c_2 - c_1 + 1} \right\rceil$ 的方案数。这个部分是普及组难度的，这里不赘述。 时间复杂度 $O(nm \log nm)$，因为递归有 $\log nm$ 层，设短边长 $x$，长边长 $y$，每层用 $x^2+xy \le 2xy$ 也即 $O(xy)$ 的时间处理了询问，每层加起来是 $O(nm)$。 练习题：[Public NOIP Round #3 (Div. 1, 提高) T4 数圈圈](https://pjudge.ac/contest/1030) 。