本文主要是介绍海啸，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
有一个沿海地区，可以看作有n行m列的城市，第i行第j列的城市海拔为h[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
思路：看题意很容易想到二维前缀和，但由于数据范围的问题，无法直接开二维数组，因此要利用一维数组模拟
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;
int n,m,d;
int mp[N],bit[N];
inline int lowbit(int x) {return x&-x;
}
inline void add(int x,int y,int num) {for(int i=x; i<=n; i+=lowbit(i))for(int j=y; j<=m; j+=lowbit(j))bit[i*m-m+j]+=num;
}
inline int sum(int a,int b) {int res=0;for(int i=a; i!=0; i-=lowbit(i))for(int j=b; j!=0; j-=lowbit(j))res+=bit[i*m-m+j];return res;
}
int main() {scanf("%d%d%d",&n,&m,&d);for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {int x;scanf("%d",&x);if(x>=d)add(i,j,1);}}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,y)-sum(a-1,y)-sum(x,b-1)+sum(a-1,b-1));}return 0;
}
这篇关于海啸的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
