C++

C++ - 2D prefix sum

_Redstone_c_

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

Question description

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.

White Rabbit has an N*m rectangular farmland, and there is a plant in each grid. The plants in row i and column j belong to type 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 die immediately.

Bai Yun wants to help White Rabbit fertilize, but the i-th plant can only adapt to the i-th type of fertilizer. If the jth fertilizer is used on the ith plant (i!=j), the plant will die immediately.

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]].

Now Baiyun plans to apply chemical fertilizer t times. In the i-th plan, Baiyun will use k[i]-th fertilizer to fertilize all plants [x1[i]…x2[i], [y1[i]…y2[i]] in a rectangular area.

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

White Rabbit wonders how many plants will eventually die if fertilized according to the expected White Cloud plan.

Enter description

  • The first line of input contains 3 integers n,m,T(n*m<=1000000,T<=1000000)
  • The first line of input contains 3 integers 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.
  • For the next n rows, each row contains m integers in the range [1, n*m], representing the plant type in each grid.
  • For the next T lines, the i-th line contains 5 integers
  • For the next T rows, row i contains 5 integers
  • x1,y1,x2,y2,k(1<=x1<=x2<=n,1<=y1<=y2<=m,1<=k<=n*m)

Output description

  • Print an integer, denoting the number of plants which would die.
  • Print an integer representing the number of plants that will die.

Example 1

enter

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

Output

3

answer

The interval problem has only one query and is solved by prefix sum.

A pattern can be found, if the sum of the types of fertilizers in a grid is % of the plant types! =0 indicates that the plant is dead, but it can be concluded that (1+3) =0 does not meet this specification, so just use random numbers to optimize it.

Two-dimensional prefix sum formula [let the original data be a, and the prefix sum be b]

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

Complete code

#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;
}

Post Reply