P8783 [蓝桥杯 2022 省 B] 统计子矩阵 题解

双指针
双指针：维护 
[
�
,
�
]
[L,R]

枚举 
�
L , 使 
�
R 一直达到使区间值满足要求的位置，然后再右移动一次 
�
L 端点，再 不断使 
�
R 达到相应位置，这样的区间值是不断 
≥
≥ 要求值

枚举 
�
L ，使 
�
R 第一次到达区间值满足要求位置，然后再不断移动 
�
L 端点，使 
[
�
,
�
]
[L,R] 满足，这样的区间值是不断 
≤
≤ 要求值(也就是这道题要用的)

1.固定 
�
L，得到的 
≥
≥ 要求值

2.固定 
�
R，得到的 
≤
≤ 要求值； 根据变化，选择固定哪个端点，做题会更加方便

题意：

找到其中的矩阵让矩阵的和 
≤
�
≤k
一看是二维的矩阵求值，那么就会想到前缀和，但是普通前缀和又要找到矩阵起始位置和结束位置，那时间复杂度简直太大了
所以就想到降维了，变化成在 
[
�
,
�
]
[l,r] 区间内的连续和 
≤
�
≤k ;那么区间求值，就能想到双指针了 建议先看 P1638 逛画展 了解下双指针的
然后就开始愉快的写代码了

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int a[505][505],s[505][505];
int b[505];
signed main(){
    
    int n,m,k,ans=0;
    cin >> n >> m >> k;
    
    for(int i = 1 ; i <= n ; ++i )
        for(int j = 1 ; j <= m ; ++j )
            cin >> a[i][j];
    
    for(int j = 1 ; j <= m ; ++j )
        for(int i = 1 ; i <= n ; ++i )
            s[i][j]=s[i-1][j]+a[i][j];//按列前缀和，s[i][j]=a[1][j]+a[2][j]+...+a[i][j];

    for(int ii = 1 ; ii <= n ; ++ii ){  
                
        for(int i = ii ; i <= n ; ++i ){  
            
            for(int j = 1 ; j <= m ; ++ j ) b[j]=s[i][j]-s[ii-1][j];//压成一维  是从i行到j行的和； 
                
            int L=1,R=0,sum=0;//双指针 r=0初始化，所以下面while里每次R++ ps：while要R<n防止R++后越界 
            
            while(R<m){//如果右端点没越界 
                
                R++;
                
                sum+=b[R];//更新区间值 
                
                if(sum <= k) ans+=(R-L+1);//如果区间值满足了条件，所以个数就是R-L+1个 
                
                else {//如果区间值大了，那么移动左端点，然后再不断移动右端点，使区间和满足条件也就是 sum≤k时 
                    
                    while(sum > k ){
                        sum-=b[L];//更新左端点 使区间和<=k 
                        L++;
                    }
                    
                    ans+=R-L+1;
                    
                }
                
            }
            
        }
            
    }
    
    cout << ans;
    return 0;
}