题目描述 运飞艇源码出售QQ2952777280【话仙源码论坛】hxforum.com【木瓜源码论坛】papayabbs.com
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(nm<=1000000,T<=1000000)
For the next n lines,each line contains m integers in range[1,nm] 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<=nm)
输出描述:
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
复制代码
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,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 <= nm; i++)a[i] = i;
19 random_shuffle(a+1,a+nm+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,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 }
