牛客寒假算法基础集训营6 E海啸（一维数组模拟二维数组，二维前缀和）
链接：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≤106= 1≤q≤105 0≤d,h[i][j]≤109 1≤a≤x≤n,1≤b≤y≤m
首先是开数组的问题，n*m小于1e6，不可能直接开二维数组，听说可以用vector，不过我不太熟这个orz
所以根据二维数组的存储方式，开一个一维数组（……）
即（i，j）为a[i*(m+1)+j]（不占用第0位）
其次这道题，很容易看出是二维前缀和，简单介绍一下二维前缀和，摘自：https://blog.****.net/k_r_forever/article/details/81775899
给定一个n*m大小的矩阵a，有q次询问，每次询问给定x1,y1,x2,y2四个数，求以(x1,y1)为左上角坐标和(x2,y2)为右下角坐标的子矩阵的所有元素和。注意仍然包含左上角和右下角的元素。
怎么做呢？为了方便你们理解，我画个图吧。
图画的很丑，希望不要介意。如图所示，按题目要求，我们每次要求的答案就是红色圆圈所在的区域的值（注意，这里的x1,x2表示行，y1,y2表示列),对比上面这张图我们能够发现红色区域的值等于四个区域的值减去（白色区域+黑色区域），再减去（白色区域+蓝色区域)，最后因为白色区域被减了两次，我们需要再加回来。所以ans=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]；(注意，此时的a数组代表的是前缀和)。
有了这一步就很简单了orz
以下代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#define ll long long
using namespace std;
int s[10000100]={0};
int main()
{
int n,m,d;
// ios::sync_with_stdio(false);
scanf("%d %d %d",&n,&m,&d);//n行m列，海水高度
int i,j,x;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&x);
s[i*(m+1)+j]=s[i*(m+1)+j-1]+s[(i-1)*(m+1)+j]-s[(i-1)*(m+1)+j-1];
// vec[i][j]=vec[i][j-1]+vec[i-1][j]-vec[i-1][j-1];
if(x>=d){
s[i*(m+1)+j]++;
}
}
}
// for(i=1;i<=n;i++){
//
// for(j=1;j<=m;j++){
//
// cout<<s[i*(m+1)+j]<<" ";
//
// }
//
// cout<<endl;
//
// }
int q;
scanf("%d",&q);
while(q--){
int a,b,x,y;
scanf("%d %d %d %d",&a,&b,&x,&y);//从第a行第b列到第x行第y列的矩形地区中，有多少地区不会被淹没。
printf("%d\n",s[x*(m+1)+y]+s[(a-1)*(m+1)+b-1]-s[(a-1)*(m+1)+y]-s[x*(m+1)+b-1]);
// cout<<vec[x][y]+vec[a-1][b-1]-vec[a-1][y]-vec[x][b-1]<<endl;
}
return 0;
}