二维前缀和 + new 二维数组

题目链接：https://ac.nowcoder.com/acm/contest/332/E


思考：只要求二维前缀和(淹没为1，没有淹没为0)对于每次询问，只需要O(1)的时间。

//二维前缀和
//把s[0][i]和s[i][0]全部置为0
//s[i-1][j-1]加重复了，必须减去。
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

我们可以注意这个数据范围。 数组必须动态申请

//动态申请二维数组
int **a;
a=new int *[n+10];
for(int i=0;i<=n;i++)
{
    a[i]=new int [m+10];
}

还有对每次询问

//对于区间(i, j), (x, y)区间的和
//s[i-1][j-1]减重复了，必须加上。
s[x][y]-s[i-1][y]-s[x][j-1]+s[i-1][j-1]

全部代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//#define p1 first
//#define p2 second
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map
 
int main()
{
    int n, m, d, q;
    scanf("%d%d%d",&n,&m,&d);
    int **a;
    int **s;
    a=new int *[n+10];
    s=new int *[n+10];
    for(int i=0;i<=n;i++)
    {
        a[i]=new int [m+10];
        s[i]=new int [m+10];
    }
    for(int i=1;i<=n;i++)
    {
        s[i][0]=0;
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]<d)
            {
                a[i][j]=0;
            }
            else
            {
                a[i][j]=1;
            }
        }
    }
    s[0][0]=0;
    for(int i=0;i<=m;i++)
    {
        s[0][i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        s[1][i]=s[1][i-1]+a[1][i];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
        }
    }
    scanf("%d",&q);
    while(q--)
    {
        int i, j, x, y;
        scanf("%d%d%d%d",&i,&j,&x,&y);
 
        printf("%d\n",s[x][y]-s[i-1][y]-s[x][j-1]+s[i-1][j-1]);
    }
 
    return 0;
}