![[蓝桥杯 2022 省 B] 统计子矩阵——炎泽汐の Blog](https://www.xn--920a971a.top/wp-content/uploads/2023/03/2023030614072920.png "[蓝桥杯 2022 省 B] 统计子矩阵——炎泽汐の Blog")
本题纯暴力的复杂度过高，首先枚举左上顶点和右下顶点的复杂度就达到了 O(n^4)级别的复杂度，再计算子矩阵的和，复杂度又达到了 O(n^6)，显然是非常容易爆掉的。
优化以后的思路大概就是前缀和+二分查找优化，这样可以降到 O(n^3logn)的复杂度，首先构建二维前缀和矩阵，这样可以用 O(1)级别的复杂度来计算子矩阵的和。其次我们考虑对枚举子矩阵的优化，首先枚举行的组合是不可避免的，左列的复杂度也不可避免，但是右边界可以通过二分查找的方法来优化，最终完成优化。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e2+3;
ll sum[maxn][maxn];
int main(){
int n,m,k,t;
cin>>n>>m>>k;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin>>t;
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t;
}
}
ll ans = 0;
for(int i = 1;i <= n;i++){
for(int j = i;j <= n;j++){
for(int l = 1,r = 1;r <= m;r++){
while(l<=r && sum[j][r]-sum[i-1][r]-sum[j][l-1]+sum[i-1][l-1]>k)
l++;
ans += r-l+1;
}
}
}
cout<<ans<<endl;
return 0;
}
