6E.海啸（C++）

海啸（C++）

点击做题网站链接

题目描述
有一个沿海地区，可以看作有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个询问的答案。

示例1
输入
3 3 3
1 2 3
2 1 5
4 3 2
2
1 2 2 3
2 1 3 3

输出
2
3

备注:
$1\le n\times m\le 10^6$
$1\le q\le 10^5$
$0\le d,h[i][j]\le 10^9$
$1\le a\le x\le n,1\le b\le y\le m$

题目思路：

参考图片来源https://blog.csdn.net/qq_40564464/article/details/86817536

1. 用 s[x][y] 表示 (1,1) 到 (x,y) 的答案，则 (a,b) 到 (x,y) 的答案 =s[x][y]+s[a-1][b-1]-s[a-1][y]-s[x][b-1] 。即 A = D - B - C + 阴影部分(注意：B、C、阴影部分并不包括A的边界）
   

2. 所以只要求 s[x][y] 即可。
   而 s[x][y] 可以通过两次计算前缀和得到。

   补充：
   前缀和、前缀积也称前缀和数组，前缀积数组。
   给一数组A，
   前缀和：新建一数组B，数组中每一项B[i]保存A中[0…i]的和；
   后缀和：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的和；
   前缀积：新建一数组B，数组中每一项B[i]保存A中[0…i]的积；
   后缀积：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的积；

3. 可以得出一个递推式：s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + ( s[i][j] >= d ? 1 : 0 )

4. 还有一个问题就是只保证了 $n\ast m\le 10^6$ ，怎么开数组？
   第一种方法如下：

int n,m;
cin >> n >> m;
int a[n+5][m+5];

第二种方法是动态数组，可用vector实现。
vector< type> v (size,value);

参考代码来源https://blog.csdn.net/qq_40564464/article/details/86817536

//申请一维数组v，大小为n，初始化为0
vector<int> v(n,0)//申请二维数组v，大小为n×m，初始化为0
vector<vector<int> > v(n,vector<int>(m,0))

本博客给出的代码使用第一种方法。

解题代码：

#include <iostream>
#include <cstring>//memset的头文件
using namespace std;
int main()
{ios::sync_with_stdio(0);//不用这个加速，C++代码超时int n,m,d,q,a,b,x,y;cin >> n >> m >> d;int s[n+5][m+5];memset(s,0,sizeof(s));//全部元素初始化为0for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){int t;cin >> t;if( t>=d ) s[i][j]=1;//如果城市没有被淹，就赋值为1；被淹了，则为0s[i][j] = s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];//前缀和}cin >> q;while(q--){cin >> a >> b >> x >> y;int sum = s[x][y]-s[x][b-1]-s[a-1][y]+s[a-1][b-1];//前缀和cout << sum << endl;}
}