鏈接：https://ac.nowcoder.com/acm/problem/21862
來源：牛客網(wǎng)

時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld
題目描述
有一個(gè)沿海地區(qū)，可以看作有n行m列的城市，第i行第j列的城市海拔為h[i][j]。
由于沿海，所以這個(gè)地區(qū)經(jīng)常會(huì)發(fā)生海嘯。
海嘯發(fā)生時(shí)，部分城市會(huì)被淹沒，具體來說，海水高度會(huì)達(dá)到d，因此海拔低于d的城市都會(huì)被淹沒。
現(xiàn)在有q次詢問，每次問你一個(gè)矩形區(qū)域中，有多少城市不會(huì)被淹沒。
輸入描述:
第一行三個(gè)整數(shù)n,m,d，具體含義見題目描述。
接下來n行，每行m個(gè)整數(shù)，其中第i行第j列的整數(shù)為h[i][j]，具體含義見題目描述。
第n+2行一個(gè)整數(shù)q，表示詢問數(shù)。
接下來q行，每行四個(gè)整數(shù)a,b,x,y，
表示詢問從第a行第b列到第x行第y列的矩形地區(qū)中，有多少地區(qū)不會(huì)被淹沒。
即有多少個(gè)i,j，滿足a≤i≤x,b≤j≤y ，且h[i][j]≥d 。
輸出描述:
共q行，第i行一個(gè)整數(shù)，表示第i個(gè)詢問的答案。
示例1
輸入
復(fù)制

3 3 3 1 2 3 2 1 5 4 3 2 2 1 2 2 3 2 1 3 3

輸出
復(fù)制

2 3

備注:
1≤n×m≤1e6

1≤q≤1e5

0≤d,h[i][j]≤1e9

1≤a≤x≤n,1≤b≤y≤m

思路：

輸入的時(shí)候就可以判斷出會(huì)不會(huì)淹沒，
所以輸入的時(shí)候預(yù)處理出一個(gè)0,1矩陣，1代表不會(huì)淹沒（h[i][j] >= d）
詢問次數(shù)很多，每次我們都要輸出要求的那個(gè)子矩陣的和，
很明顯還需要預(yù)處理一下，我們需要維護(hù)一個(gè)二維前綴和：
s[i][j]為(0,0)到(i,j)的前綴和
假設(shè)現(xiàn)在我們要求如下圖中的子矩陣A的和：
那么：
A = D - B - C + (B∩C)

即 ans = s [x][y]- s[a-1][y] - s[x][b-1] + s[a-1][b-1]
預(yù)處理前綴和數(shù)組s，是ans的逆過程
s[i][j] = (val>=d)+s[i-1][j]+s[i][j-1]-s[i-1][j-1]
AC_code:

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

way2用二維數(shù)狀數(shù)組：
數(shù)狀數(shù)組在求前綴和方面比較強(qiáng)大，
本題也可以用二維樹狀數(shù)組來維護(hù)。
AC_code:

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6+2; vector<int> a[MAXN]; int n,m,d; void init() {for(int i = 1; i<= n; i++){a[i].push_back(0);for(int j = 1; j <= m; j++){a[i].push_back(0);}} } int lowbit(int x) {return x&-x; } void add(int x,int y,int v) {for(int i = x; i <= n; i+=lowbit(i)){for(int j = y; j <= m; j+=lowbit(j)){a[i][j] += v;}} } int sum(int x,int y) {int s = 0;for(int i = x; i > 0; i-=lowbit(i)){for(int j = y; j > 0; j-=lowbit(j)){s += a[i][j];}}return s; }int main() {std::ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m>>d;init();int val;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin>>val;if(val >= d) add(i,j,1);}}int t,a,b,x,y;cin>>t;while(t--){cin>>a>>b>>x>>y;int ans = sum(x,y)-sum(x,b-1)-sum(a-1,y)+sum(a-1,b-1);cout<<ans<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的海啸（二维前缀和/二维树状数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。