二维前缀和-白红宇

二维前缀和

阅读量：4629 次

发布时间：2019-06-09

本文共 1215 字，大约阅读时间需要 4 分钟。

题目链接： 海啸

题目描述

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

输入

3 3 31 2 32 1 54 3 221 2 2 32 1 3 3

输出

备注:

1<=n*m<=10^6

1<=q<=10^5

0<=d,h[i][j]<=10^9

1<=a<=x<=n,1<=b<=y<=m

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
             7 #include
             
               8 #include
              
                9 using namespace std;10 #define ll long long11 const int inf=99999999;12 const int mod=1e9+7;13 const int maxn=1e6+2;14 int main()15 {16 ios::sync_with_stdio(false);17 int n,m,d;18 cin>>n>>m>>d;19 int sum[n+1][m+1];20 memset(sum,0,sizeof(sum));21 int num;22 //根据题意导入二维数组23 for(int i=1;i<=n;i++)24 {25 for(int j=1;j<=m;j++)26 {27 cin>>num;28 if(num
               
                >op;44 int x1,y1,x2,y2;45 while(op--)46 {47 cin>>x1>>y1>>x2>>y2;48 cout<
                
                 <