二维区间前缀和更新与维护

题目描述

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 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.
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]].
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)
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 T lines, the i-th line contains 5 integers 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

输入

复制

输出

复制

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 using namespace __gnu_cxx;
 8 
 9 const int N = 1e6+10;
10 int n,m,q;
11 int a[N];
12 int vis[N];
13 vector<long long>v[N],cnt[N],sum[N];
14 int main()
15 {
16     while(scanf("%d%d%d",&n,&m,&q)!=EOF)
17     {
18         for(int i = 1; i <= n*m; i++)a[i] = i;
19         random_shuffle(a+1,a+n*m+1);
20         for(int i = 0; i <= n+1; i++)
21         {
22             v[i].resize(m+5);
23             cnt[i].resize(m+5);
24             sum[i].resize(m+5);
25         }
26         for(int i = 1; i <= n; i++)
27         {
28             for(int j = 1; j <= m; j++)
29             {
30                 scanf("%d",&v[i][j]);
31                 v[i][j] = a[v[i][j]];
32                 cnt[i][j] = 0;
33                 sum[i][j] = 0;
34             }
35         }
36         int x1,x2,y1,y2,k;
37         while(q--)
38         {
39             scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
40             sum[x1][y1] += a[k];
41             sum[x1][y2+1]-=a[k];
42             sum[x2+1][y1]-=a[k];
43             sum[x2+1][y2+1]+=a[k];
44             cnt[x1][y1]++;
45             cnt[x1][y2+1]--;
46             cnt[x2+1][y1]--;
47             cnt[x2+1][y2+1]++;
48         }
49         int answer = 0;
50         for(int i = 1; i <= n; i++)
51         {
52             for(int j = 1; j <= m; j++)
53             {
54                 sum[i][j] += sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
55                 cnt[i][j] += cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
56                 if(sum[i][j]!=cnt[i][j]*v[i][j])answer++;
57             }
58         }
59         cout<<answer<<endl;
60     }
61     return 0;
62 }