题目大意:
给出一个n*m的田地矩阵，每个格子上种着一种植物。给格子施肥t次，每一次给出五个数字，x1，y1，x2，y2，k，要施肥的区域坐标和要施的肥料种类。如果植物和施肥种类不匹配，植物会死亡。问最终会死多少个植物。
思路:
- 判断 一个植物 死不死, 判断植物种类*施肥次数==施肥种类总和
- 某些情况也会出现相等: 1 2 3 4 5, 种类为3
- 因此 通过rand() 种类一个新值, 因为rand 是离散化的, 所以这个新值就不会出现
- 利用二维树状数组维护 种类和 和次数
- 这里是 区间修改, 单点查询 (差分的思想)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+10; int a[maxn],cnt[maxn],ran[maxn]; ll sum[maxn]; int n,m,t,x,y,z,w,k; int lowbit(int x){ return x&-x; } void update(int x,int y,int add,int d) { int tempy=y; while(x<=n) { y=tempy; while(y<=m) { sum[(x-1)*m+y-1]+=add; cnt[(x-1)*m+y-1]+=d; y+=lowbit(y); } x+=lowbit(x); } } bool query(int x,int y) { ll rets=0,retc=0; int tmp=ran[a[(x-1)*m+y-1]]; int tempy=y; while(x>0){ y=tempy; while(y>0){ rets+=sum[(x-1)*m+y-1]; retc+=cnt[(x-1)*m+y-1]; y-=lowbit(y); } x-=lowbit(x); } if(rets==retc*tmp) return true; else return false; } void init(){ for(int i=0;i<maxn;i++){ ran[i]=rand(); } } int main(){ init(); while(scanf("%d%d%d",&n,&m,&t)==3){ memset(cnt,0,sizeof(cnt)); memset(sum,0,sizeof(sum)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&a[i*m+j]); } } for(int i=0;i<t;i++){ scanf("%d%d%d%d%d",&x,&y,&z,&w,&k); update(z+1,w+1,ran[k],1); update(x,y,ran[k],1); update(x,w+1,-ran[k],-1); update(z+1,y,-ran[k],-1); } int ans=n*m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) if(query(i,j)) ans--; } printf("%d\n",ans); } return 0; }