二维前缀和
题目链接：https://ac.nowcoder.com/acm/problem/21862
海啸
题目描述
有一个沿海地区，可以看作有n行m列的城市，第i行第j列的城市海拔为h[i][j]。由于沿海，所以这个地区经常会发生海啸。
海啸发生时，部分城市会被淹没，具体来说，海水高度会达到d，因此海拔低于d的城市都会被淹没。
现在有q次询问，每次问你一个矩形区域中，有多少城市不会被淹没。
输入描述:
第一行三个整数n,m,d，具体含义见题目描述。
接下来n行，每行m个整数，其中第i行第j列的整数为h[i][j]，具体含义见题目描述。
第n+2行一个整数q，表示询问数。
接下来q行，每行四个整数a,b,x,y，
表示询问从第a行第b列到第x行第y列的矩形地区中，有多少地区不会被淹没。
即有多少个i,j，满足 a<=i<=x,b<=j<=y，且 h[i][j]>d。
输出描述:
共q行，第i行一个整数，表示第i个询问的答案。
输入
3 3 3
1 2 3
2 1 5
4 3 2
2
1 2 2 3
2 1 3 3
输出
2
3
备注:
1<=n*m<=10^6
1<=q<=10^5
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。0<=d,h[i][j]<=10^9
1<=a<=x<=n,1<=b<=y<=m
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cmath>
5 #include<algorithm>
6 #include<map>
7 #include<set>
8 #include<vector>
9 using namespace std; 10 #define ll long long
11 const int inf=99999999; 12 const int mod=1e9+7; 13 const int maxn=1e6+2; 14 int main() 15 { 16 ios::sync_with_stdio(false); 17 int n,m,d; 18 cin>>n>>m>>d; 19 int sum[n+1][m+1]; 20 memset(sum,0,sizeof(sum)); 21 int num; 22 //根据题意导入二维数组
23 for(int i=1;i<=n;i++) 24 { 25 for(int j=1;j<=m;j++) 26 { 27 cin>>num; 28 if(num<d) 29 sum[i][j]=0; 30 else
31 sum[i][j]=1; 32 } 33 } 34 //积二维前缀和
35 for(int i=1;i<=n;i++) 36 { 37 for(int j=1;j<=m;j++) 38 { 39 sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; 40 } 41 } 42 int op; 43 cin>>op; 44 int x1,y1,x2,y2; 45 while(op--) 46 { 47 cin>>x1>>y1>>x2>>y2; 48 cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl; 49 } 50 return 0; 51 }
更多精彩
