统计子矩阵

一、题目描述

P8783 [蓝���杯 2022 省 B] 统计子矩阵

二、算法简析

2.1 二维前缀和

我们知道，只要确定了矩阵的左上顶点和右下顶点，一个矩阵就被固定了。因此，我们可以遍历这两个顶点，达到遍历所有子矩阵的目的，复杂度会达到 O ( N 2 ∗ M 2 ) O(N^2*M^2) O(N2∗M2)。确定了子矩阵，就要判断子矩阵的值是否不大于 K K K。 如何能高效地得到子矩阵的值呢？答案是二维前缀和。

与普通的前缀和不同，二维前缀和 psum[i][j] = \text{psum[i][j]}= psum[i][j]= 左上顶点 ( 1 , 1 ) (1, 1) (1,1)、右下顶点 ( i , j ) (i, j) (i,j) 确定的子矩阵的值。通过以下表达式，可以得到二维前缀和：

psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + A[i][j] \text{psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + A[i][j]} psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + A[i][j]

有了二维前缀和，就可以以 O ( 1 ) O(1) O(1) 确定左上角 ( x 1 , y 1 ) (x1, y1) (x1,y1)、右下角 ( x 2 , y 2 ) (x2, y2) (x2,y2) 的子矩阵的值：

matrix_val = psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1] \text{matrix\_val = psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1]} matrix_val = psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1]

但是，该算法的复杂度仍然有 O ( N 2 ∗ M 2 ) O(N^2*M^2) O(N2∗M2)，会 LTE。

2.2 压缩维度 + 双指针

压缩维度：我们可以把二维矩阵压缩至一维：画两条线，high 表示矩阵上界（左上点只能在该行）、low表示矩阵下界（右下点只能在该行）。因此，由 high 和 low 确定的子矩阵只能由列矩阵组合而成，所以按列压缩，即按列求和。

通过遍历 high 和 low，我们可以得到所有组成子矩阵的列矩阵。

双指针：通过上文的压缩，我们得到了“子矩阵的零件”。为了得到该情况下的所有子矩阵，肯定要用双指针遍历压缩数组，得到所有组合方式。

int B[4];   // 压缩后的结果for (int i = 0; i  
显然，指针 j 发生了回溯，导致复杂度达到了                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)。如何避免发生回溯呢？利用单调性，我们可以把复杂度降为                                    O                         (                         n                         )                              O(n)                  O(n)。
我们规定                                    area(left, right) = B[left] + B[left + 1] + ... + B[right]                              \text{area(left, right) = B[left] + B[left + 1] + ... + B[right]}                  area(left, right) = B[left] + B[left + 1] + ... + B[right]。
若                                    area(left, right) tmp += B[right];if (tmp while (tmp  K){tmp -= B[left];left++;}ans += right - left + 1;}} int ret = 0;char ch = getchar();while (ch