C++统计子矩阵 前缀和+双指针

解题思路:如果只使用前缀和以及暴力 是拿不到全部的分数的，可以使用双指针优化内层循环，确定上下边界，如何枚举左右

注意事项:

参考代码:

#include<iostream>

#define N 505

using namespace std;

typedef long long ll;

int a[N][N];

int n,m,k;

ll ans=0;

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    cin>>n>>m>>k;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            cin>>a[i][j];

            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];//注意有减一

        }

    }

    //读入前缀和

    //TODO 确定上下边界，利用双指针遍历左右边界

    for(int i=1; i<=n; i++){

        for(int j=i; j<=n; j++){

            int l=1,r=1;

            while(l<=r&&r<=m){//设立好边界 r<=m双指针向后遍历

                while(a[j][r]-a[j][l-1]-a[i-1][r]+a[i-1][l-1]>k){

                    l++;//当超出时l右移

                }

                if(l<=r){ans+=r-l+1;}//贡献是r-l+1 将r边看做是固定的，那么子矩阵就只有r-l+1

                ++r;

            }

        }

    }

    cout<<ans;

}