统计子矩阵 前缀和 滑动窗口

统计子矩阵问题描述给定一个N × M N \times MN×M的矩阵A AA统计有多少个子矩阵最小1 × 1 1 \times 11×1最大N × M N \times MN×M满足子矩阵中所有数的和不超过给定的整数K KK。输入格式第一行包含三个整数N NN,M MM和K KK。之后N NN行每行包含M MM个整数代表矩阵A AA。输出格式一个整数代表答案。样例输入3 4 10 1 2 3 4 5 6 7 8 9 10 11 12样例输出19样例说明满足条件的子矩阵一共有 19 个包含大小为1 × 1 1 \times 11×1的有 10 个。大小为1 × 2 1 \times 21×2的有 3 个。大小为1 × 3 1 \times 31×3的有 2 个。大小为1 × 4 1 \times 41×4的有 1 个。大小为2 × 1 2 \times 12×1的有 3 个。评测用例规模与约定对于30 % 30\%30%的数据N , M ≤ 20 N, M \leq 20N,M≤20。对于70 % 70\%70%的数据N , M ≤ 100 N, M \leq 100N,M≤100。对于100 % 100\%100%的数据1 ≤ N , M ≤ 500 1 \leq N, M \leq 5001≤N,M≤5000 ≤ A i j ≤ 1000 0 \leq A_{ij} \leq 10000≤Aij​≤10001 ≤ K ≤ 250000000 1 \leq K \leq 2500000001≤K≤250000000。问题分析看到矩阵和自然而然想到二维前缀和二维前缀和是一种预处理技术可以在O ( 1 ) O(1)O(1)时间内计算任意子矩阵的和。定义前缀和数组S SS其中S [ i ] [ j ] S[i][j]S[i][j]表示从( 1 , 1 ) (1,1)(1,1)到( i , j ) (i,j)(i,j)的子矩阵的和。预处理公式为S [ i ] [ j ] S [ i − 1 ] [ j ] S [ i ] [ j − 1 ] − S [ i − 1 ] [ j − 1 ] A [ i ] [ j ] S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] A[i][j]S[i][j]S[i−1][j]S[i][j−1]−S[i−1][j−1]A[i][j]计算子矩阵( x 1 , y 1 ) (x1,y1)(x1,y1)到( x 2 , y 2 ) (x2,y2)(x2,y2)的和的公式为sum S [ x 2 ] [ y 2 ] − S [ x 1 − 1 ] [ y 2 ] − S [ x 2 ] [ y 1 − 1 ] S [ x 1 − 1 ] [ y 1 − 1 ] \text{sum} S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]sumS[x2][y2]−S[x1−1][y2]−S[x2][y1−1]S[x1−1][y1−1]但是就算是二维前缀和因为要枚举( x 1 , y 1 ) (x1,y1)(x1,y1)( x 2 , y 2 ) (x2,y2)(x2,y2)四个变量时间复杂度为O ( N 2 M 2 ) O(N^2M^2)O(N2M2)仍旧不能满足题目要求优化思路可以将问题分解为固定子矩阵的行范围然后对列进行优化。具体步骤如下枚举行范围枚举子矩阵的上下边界r 1 r1r1和r 2 r2r21 ≤ r 1 ≤ r 2 ≤ N 1 \leq r1 \leq r2 \leq N1≤r1≤r2≤N。压缩列对于固定的r 1 r1r1和r 2 r2r2将每一列j jj的和压缩为一个一维数组c o l [ j ] col[j]col[j]表示第j jj列从r 1 r1r1到r 2 r2r2的和。滑动窗口在压缩后的一维数组上使用滑动窗口或前缀和加二分的方法统计满足条件的子矩阵数量。举例滑动窗口方法对于压缩后的一维数组c o l colcol使用滑动窗口可以在O ( M ) O(M)O(M)时间内统计满足条件的子矩阵数量。具体步骤如下初始化窗口的左右指针l e f t leftleft和r i g h t rightright以及当前和c u r r e n t _ s u m current\_sumcurrent_sum。遍历r i g h t rightright从1 11到M MM累加c o l [ r i g h t ] col[right]col[right]到c u r r e n t _ s u m current\_sumcurrent_sum。如果c u r r e n t _ s u m K current\_sum Kcurrent_sumK移动l e f t leftleft指针并减去c o l [ l e f t ] col[left]col[left]直到c u r r e n t _ s u m ≤ K current\_sum \leq Kcurrent_sum≤K。统计以r i g h t rightright为右端点的满足条件的子矩阵数量为r i g h t − l e f t 1 right - left 1right−left1。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn,m,k;cinnmk;vectorvectorinta(n1,vectorint(m1));vectorvectorintsum(n1,vectorint(m1,0));for(inti1;in;i){for(intj1;jm;j){cina[i][j];}}longlongans0;// 先计算列的前缀和col_sum[i][j] 表示第 j 列前 i 行的和vectorvectorintcol_sum(n1,vectorint(m1,0));for(intj1;jm;j){for(inti1;in;i){col_sum[i][j]col_sum[i-1][j]a[i][j];}}ans0;// 枚举上边界 ifor(inti1;in;i){// 枚举下边界 afor(intai;an;a){// 现在 col_sum[a][j] - col_sum[i-1][j] 是第 j 列从 i 到 a 的和intl1;longlongcur0;for(intr1;rm;r){curcol_sum[a][r]-col_sum[i-1][r];while(curk){cur-col_sum[a][l]-col_sum[i-1][l];l;}ansr-l1;}}}coutansendl;return0;}复杂度分析预处理前缀和O ( N M ) O(NM)O(NM)。枚举行范围O ( N 2 ) O(N^2)O(N2)。滑动窗口O ( M ) O(M)O(M)每对行范围。总复杂度O ( N 2 M ) O(N^2M)O(N2M)对于N , M ≤ 500 N, M \leq 500N,M≤500可以接受。