题目链接点这里
这个题输入类型是第一次见，并没有把n和m的具体范围给你，但是给了n*m的范围，武断的设为1e6*1e6的二维数组铁铁WA，就将二维数组转换为一维数组
题目类型属于二维数组前缀和，有um[i][j]=sum[i?1][j]+sum[i][j?1]?sum[i?1][j?1]+a[i][j]
求矩阵(a,b)到(x,y)的矩阵的和可以用sum[x][y]?sum[x][b?1]?sum[a?1][y]+sum[a?1][b?1]
在前期处理的时候，将水位超过d的设为1，否则设为0
代码如下：
#include <bits/stdc++.h> using namespace std; const int inf=1<<30; typedef long long ll; const double pi=acos(-1); const int mod=1e9+7; const int maxn=2e6; int h[maxn]; int sum[maxn]; int main(){ int n,m,d;scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int t;scanf("%d",&t); t=t>=d?1:0; h[i*(m+1)+j]=t; sum[i*(m+1)+j]=sum[(i-1)*(m+1)+j]+sum[i*(m+1)+j-1]-sum[(i-1)*(m+1)+j-1]+h[i*(m+1)+j]; } } int q;scanf("%d",&q); while(q--){ int a,b,x,y;scanf("%d%d%d%d",&a,&b,&x,&y); printf("%d\n",sum[x*(m+1)+y]-sum[(a-1)*(m+1)+y]-sum[x*(m+1)+b-1]+sum[(a-1)*(m+1)+b-1]); } return 0; }
原文：https://www.cnblogs.com/qingjiuling/p/10349444.html