统计子矩阵_（前缀和，双指针）

原题链接：4405. 统计子矩阵 - AcWing题库

题意：给定大小矩阵，对矩阵的每个子矩阵做判断，判断其全部值加起来会不会大于给定的k，统计不大于的子矩阵有多少

思路

总之前缀和，你最好不要连这个都看不出来。

发现计算的量太多了，一个矩阵四个自由度，每个都是n，如果全部遍历就是$n^4$ 前缀和可以减少计算量，但是还是不够

前缀和之后，发现也是四个维度，因为子矩阵可以存在在矩阵的任何位置

那怎么办？试试看如果减去一维能不能做，发现可以，复杂度在一亿以内。

用双指针可以去掉一维，判断能不能用，要求当一边变化，另一边也单调变化。 当遍历例如左右时，左边不变，逐步增大子矩阵的大小，当大于k时，发现，再变大也大于k，只能变小，也就是左边界向右边移动，直到不大于k时，可以继续计数。即可知单调变化。

实现

先判断双指针怎么用？ 使用双指针一般是 左右 边界。

那在计算时就可以先不统计行的前缀和，只需要列的前缀和，因为行的前缀和可以在边界变动的时候求，同时验证是否大于k，而因为遍历左右维度，上下维度的值得在外循环遍历，也就是在计算矩阵大小的时候，需要上下维度，也就是列的值提前计算好才可以直接遍历上下维度，再遍历左右维度求解

看代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
const int N = 1010;
 
int s[N][N];
 
 
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            // 只求列的前缀和
            cin >> s[i][j];
            s[i][j] += s[i-1][j];
        }
        
    LL ans = 0;
    //枚举行
    for(int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)
        {
            LL sum = 0;
            for(int l = 1, r = 1; r <= m; r ++)
            {
                //双指针化掉一维
                //计算当前所选矩阵的值
                sum += s[j][r] - s[i-1][r];
                while(sum > k)
                {
                    //如果当前大于k了，就移动l来让值小于k，因为上下边界固定
                    sum -= s[j][l] - s[i-1][l];
                    l ++;
                }
                ans += r - l + 1;
            }
        }
        
    cout << ans << endl;
    
    return 0;
}