链接：https://www.nowcoder.com/acm/contest/140/J
来源：牛客网
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
输入
2 2 2
1 2
2 3
1 1 2 2 2
2 1 2 1 1
输出
3
题意:给出一个n*m的区域,t次操作 每个点都是一种植物 t次操作区域覆盖肥料，如果区域里面的植物不等于覆盖的飞亮那么就植物死亡，求有多少植物死亡。
思路:我们将每种植物的坐标存下来，然后我也将每种肥料的覆盖区域坐标存下，在我们算每种植物贡献的时候，我们先删除同种肥料对于贡献的影响，然后再查询完再加上
最后枚举所有植物即可。
#include<bits/stdc++.h> using namespace std; #define pb push_back #define pll pair<int,int> #define mp make_pair #define ll long long const int maxn = 1000000+5; struct node { int x1,x2,y1,y2; node(int x1,int x2,int y1,int y2):x1(x1),x2(x2),y1(y1),y2(y2) {}; }; vector< vector< pll > > p; vector< vector< int > > a; vector< vector<node> > pos; int n,m; int lowbit(int x) { return x&(-x); } void add(int x,int y,int d) { for(int i=x; i<=n; i+=lowbit(i)) for(int j=y; j<=m; j+=lowbit(j)) a[i][j]+=d; } int query(int x,int y) { int ans=0; for(int i=x; i>0; i-=lowbit(i)) for(int j=y; j>0; j-=lowbit(j)) ans+=a[i][j]; return ans; } void updata(int x1,int y1,int x2,int y2,int d) { add(x1,y1,d); add(x2+1,y2+1,d); add(x1,y2+1,-d); add(x2+1,y1,-d); } int main() { int t,k,x1,x2,y1,y2; scanf("%d %d %d",&n,&m,&t); a.resize(n+1); for(int i=1; i<=n; i++) a[i].resize(m+1); p.resize(n*m+1); pos.resize(n*m+1); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { scanf("%d",&k); p[k].pb(mp(i,j)); } for(int i=1; i<=t; i++) { scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&k); pos[k].pb(node(x1,x2,y1,y2)); updata(x1,y1,x2,y2,1); } ll ans=0; for(int i=1; i<=n*m; i++) { int len=pos[i].size(); for(int j=0; j<len; j++) { updata(pos[i][j].x1,pos[i][j].y1,pos[i][j].x2,pos[i][j].y2,-1); } int len1=p[i].size(); for(int j=0; j<len1; j++) { if(query(p[i][j].first,p[i][j].second)) ans++; } for(int j=0; j<len; j++) { updata(pos[i][j].x1,pos[i][j].y1,pos[i][j].x2,pos[i][j].y2,1); } } printf("%lld ",ans); }
PS：摸鱼怪的博客分享，欢迎感谢各路大牛的指点~