[牛客竞赛] 海啸（思维）

链接：https://ac.nowcoder.com/acm/contest/332/E
来源：牛客网

题目描述

有一个沿海地区，可以看作有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 ≤ n×m ≤ 10⁶
1 ≤ q ≤ 10⁵
0 ≤ d , h[i][j] ≤ 10⁹
1 ≤ a ≤ x ≤ n , 1 ≤ b ≤ y ≤ m

---

分析：

用 s[x][y] 表示 (1,1) 到 (x,y) 的答案

那么 A = D - B - C + 阴影部分 (注意：B、C、阴影部分并不包括A的边界）

即 (a,b) 到 (x,y) 的答案 = s[x][y] - s[a-1][y] - s[x][b-1] + s[a-1][b-1] 。


那么再者就是求 s[x][y]

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

此外，因为题目仅告知1 ≤ n×m ≤ 10⁶，所以数组要动态申请，可用vector实现。

vector< type> v (size,value);

//大小为n的一维数组，且初始化为0
vector<int> v(n,0)

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

---

以下代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{	
	int n,m,d,t;
	scanf("%d %d %d",&n,&m,&d);
	vector<vector<int> > s(n+10,vector<int>(m+10,0));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&t);
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            if(t>=d)
                s[i][j]++;
		}
	}
	int q,a,b,x,y;
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d %d %d %d",&a,&b,&x,&y);
		int ans=s[x][y]-s[x][b-1]-s[a-1][y]+s[a-1][b-1];
		printf("%d\n",ans);
	}
	return 0;
}