C++

C++ – 二维前缀和

_Redstone_c_

链接：https://ac.nowcoder.com/acm/contest/140/J?&headNav=www

题目描述

White Rabbit has a rectangular farmland of n*m. In each of the grid there is a kind of plant. The plant in the j-th column of the i-th row belongs the a[i][j]-th type.

白兔有一个N*m的长方形农田，每一个格子里都有一种植物。第i行j列中的植物属于a[i][j]-th类型。

White Cloud wants to help White Rabbit fertilize plants, but the i-th plant can only adapt to the i-th fertilizer. If the j-th fertilizer is applied to the i-th plant (i!=j), the plant will immediately die.

白云想帮助白兔施肥，但第i种植物只能适应第i种肥料。如果第j种肥料用于第i种植物（i!=j），植物将立即死亡。

Now White Cloud plans to apply fertilizers T times. In the i-th plan, White Cloud will use k[i]-th fertilizer to fertilize all the plants in a rectangle [x1[i]…x2[i]][y1[i]…y2[i]].

现在白云计划施化肥t次。在i-th计划中，白云将使用k[i]-th肥料在一个矩形区域内使所有的植物施肥[x1[i]…x2[i]，[y1[i]…y2[i]]。

White rabbits wants to know how many plants would eventually die if they were to be fertilized according to the expected schedule of White Cloud.

白兔想知道，如果按照预期的白云计划施肥，最终会有多少植物死亡。

输入描述

  • The first line of input contains 3 integers n,m,T(n*m<=1000000,T<=1000000)
  • 输入的第一行包含3个整数n，m，t（n*m<=1000000，t<=1000000）
  • For the next n lines, each line contains m integers in range[1,n*m] denoting the type of plant in each grid.
  • 对于接下来的n行，每行包含m个整数，范围为[1，n*m]，表示每个网格中的植物类型。
  • For the next T lines, the i-th line contains 5 integers
  • 对于下一个T行，第i行包含5个整数
  • x1,y1,x2,y2,k(1<=x1<=x2<=n,1<=y1<=y2<=m,1<=k<=n*m)

输出描述

  • Print an integer, denoting the number of plants which would die.
  • 打印一个整数，表示将要死亡的植物数量。

示例1

输入

2 2 2
1 2
2 3
1 1 2 2 2
2 1 2 1 1

输出

3

题解

区间问题，只有一次查询，用前缀和来解。

可以找到一个规律，如果一个格子的肥的种类之和%植物种类！=0说明植物死亡，但是可以得出（1+3）=0不符合这个规范，于是使用随机数优化一下就好了。

二维前缀和公式[设原数据为a，前缀和为b]

b[i][j] = a[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

完整代码

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
const int MAXN = 1000002;
vector<int> ran;
vector<int> p[MAXN];
vector<long long> f[MAXN];
int main() {
    int n, m, t;
    srand(2333);
    for(int i = 0; i < MAXN; i++)
        ran.push_back((1LL * rand() << 15) + rand());
    scanf(%d %d %d, &n, &m, &t);
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            p[i].push_back(0);
            f[i].push_back(0);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int temp;
            scanf(%d, &temp);
            p[i][j] = ran[temp];
        }
    }
    for(int i = 0; i < t; i++) {
        int x1, y1, x2, y2, k;
        scanf(%d %d %d %d %d, &x1, &y1, &x2, &y2, &k);
        f[x1][y1] += ran[k];
        f[x1][y2 + 1] -= ran[k];
        f[x2 + 1][y1] -= ran[k];
        f[x2 + 1][y2 + 1] += ran[k];
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            if(f[i][j] % p[i][j]) ans++;
        }
    }
    printf(%lld, ans);
    return 0;
}

发表回复