CF713D 题解

题意

给一个 \(01\) 矩阵，多次求在给定区间内最大的全 \(1\) 正方形边长。

思路

容易想到二分：

先预处理出以每个位置为右下角的最大合法正方形的边长 \(mx_{i,j}\)，然后对于每个询问，我们二分边长 \(mid\)，设当前询问的区间左上角为 \((x_1,y_1)\)，右下角为 \((x_2,y_2)\)，则能取到 \(mid\) 当且仅当 在以 \((x_1+mid-1,y_1+mid-1)\) 为 \((x_2,y_2)\) 对角的矩形中有 \(mx_{i,j}\) 不小于 \(mid\) 的位置。

于是就可以用二维 ST 表。时间复杂度 \(O(n^2\log^2n+t\log n)\)（假设 \(n\) 与 \(m\) 同级）空间复杂度 \(O(n^2\log^2n+t)\)。

还有另一种思路：整体二分。

我们将所有询问一起处理，对于当前的 \(mid\)，把 \(mx \ge mid\) 的位置看成 \(1\)，否则为 \(0\)，一个询问能取到 \(mid\) 当且仅当 在以 \((x_1+mid-1,y_1+mid-1)\) 为 \((x_2,y_2)\) 对角的矩形中有 \(1\)，可以使用前缀和优化，时间复杂度 \(O(n^3 + t\log n)\)（假设 \(n\) 与 \(m\) 同级），但是每次我们需要处理新值的区间只有 \((mid,mid)\) 至 \((n,m)\)，所以常数比较小，也可以过。空间复杂度 \(O(n^2+t)\)。