这道题的做法很多。
二维前缀和+随机
用两个差分二维数组，一个存种类和，另一个存总次数，对于每一次撒农药操作(x1,y1,x2,y2，k)，将种类和数组的对应区域加上k，同时将总次数对应区域加上1。（关于差分二维数组，这里不多做解释。
然后，将两个差分数组做个二维的前缀和，得到每个位置的种类和与总次数。
若某位置的 种类*总次数！=种类和，则说明有别的农药，则该位置植物死亡。
但是，如果种类是初始的[1，n*m]，则可能导致 k1+k2+...+kn == ki * n，从而出现误判，因此，需要给每个种类一个随机的代号，即我们使用的其实并不是初始的种类，而是该种类的代号，这样误判的几率就会极小。
时间复杂度O(n*m)
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define m_p make_pair
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ls (root<<1)
#define rs ((root<<1)|1)
const int M=1e6+5;
const db eps=1e-8;
const int INF=0x3f3f3f3f;
const int mod=1e7;
struct FastIO//输入挂
{static const int S=200;int wpos;char wbuf[S];FastIO():wpos(0){}inline int xchar(){static char buf[S];static int len=0,pos=0;if(pos==len) pos=0,len=fread(buf,1,S,stdin);if(pos==len) exit(0);return buf[pos++];}inline int read(){int s=1,c=xchar(),x=0;while(c<=32) c=xchar();if(c=='-') s=-1,c=xchar();for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';return x*s;}~FastIO(){if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;}
}io;
int t,n,m;
int ran[M];
void init(){srand(time(0));For(i,1,M-5) ran[i]=rand()%mod+M;
}
int getid(int x,int y){if(x-1<0||y-1<0) return 0;return (x-1)*m+y;
}
int v[M],v2[M];
ll v1[M];void update(int id[],int z){v1[id[0]]+=z;v1[id[1]]+=z;v1[id[2]]-=z;v1[id[3]]-=z;
}
void update1(int id[],int z){v2[id[0]]+=z;v2[id[1]]+=z;v2[id[2]]-=z;v2[id[3]]-=z;
}
int main(){init();
// scanf("%d %d %d",&n,&m,&t);n=io.read(),m=io.read(),t=io.read();For(i,1,n){For(j,1,m){v[getid(i,j)]=io.read();//scanf("%d",&v[getid(i,j)]);}}int x,y,xx,yy,z,id[4];For(i,1,t){x=io.read(),y=io.read(),xx=io.read(),yy=io.read(),z=io.read();//scanf("%d %d %d %d %d",&x,&y,&xx,&yy,&z);id[0]=getid(xx,yy),id[1]=getid(x-1,y-1);id[2]=getid(xx,y-1),id[3]=getid(x-1,yy);update(id,ran[z]);update1(id,1);}for(int i=n;i>=1;i--){for(int j=m-1;j>=1;j--) id[0]=getid(i,j),id[1]=getid(i,j+1),v1[id[0]]+=v1[id[1]],v2[id[0]]+=v2[id[1]];}for(int i=m;i>=1;i--){for(int j=n-1;j>=1;j--) id[0]=getid(j,i),id[1]=getid(j+1,i),v1[id[0]]+=v1[id[1]],v2[id[0]]+=v2[id[1]];}int ans=0;For(i,1,n){For(j,1,m){id[0]=getid(i,j);if(v1[id[0]]!=v2[id[0]]*ran[v[id[0]]]){ans++;}}}cout<<ans<<"\n";return 0;
}
二维前缀和+二进制
也是一个不错的想法，感觉做题的意思就在于可以见识到很多自己可能想不到的思路。
首先，我们可以知道，任意两个不同的数，二进制形式下至少有一位不同。根据这一条件，我们可以将种类进行拆位，因为n*m<=1e6，所以可以拆成二十位，维护每一位的0和1个数的和。若某个位置被不同种类的农药撒过，则一定至少存在一位，该位置的种类在这一位上为1（或为0），而该位置的0（或1）的个数和在这一位上大于0。
对于每次撒农药(x1,y1,x2,y2,k)，用四十个差分二维数组，维护区域的0和1的个数。
然后，对每个数组做二维前缀和，得到每个位置的每一位的0和1的个数。
对每个位置种类的每一位进行判断，若该位为0且该位1的个数大于0，或者该位为1且该位0的个数大于0，则说明该位置的植物死亡。
时间复杂度O( n*m*log(n*m) )，log(n*m)来自拆位
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define m_p make_pair
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ls (root<<1)
#define rs ((root<<1)|1)
const int M=1e6+5;
const db eps=1e-8;
const int INF=0x3f3f3f3f;
const int mod=1e7;
struct FastIO//输入挂
{static const int S=200;int wpos;char wbuf[S];FastIO():wpos(0){}inline int xchar(){static char buf[S];static int len=0,pos=0;if(pos==len) pos=0,len=fread(buf,1,S,stdin);if(pos==len) exit(0);return buf[pos++];}inline int read(){int s=1,c=xchar(),x=0;while(c<=32) c=xchar();if(c=='-') s=-1,c=xchar();for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';return x*s;}~FastIO(){if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;}
}io;
int t,n,m;
int getid(int x,int y){if(x-1<0||y-1<0) return 0;return (x-1)*m+y;
}
int v[M],v1[2][20][M];void update(int id[],int x,int z){v1[z&1][x][id[0]]+=1;v1[z&1][x][id[1]]+=1;v1[z&1][x][id[2]]-=1;v1[z&1][x][id[3]]-=1;
}
int main(){n=io.read(),m=io.read(),t=io.read();For(i,1,n){For(j,1,m){v[getid(i,j)]=io.read();}}int x,y,xx,yy,z,id[4];For(i,1,t){x=io.read(),y=io.read(),xx=io.read(),yy=io.read(),z=io.read();id[0]=getid(xx,yy),id[1]=getid(x-1,y-1);id[2]=getid(xx,y-1),id[3]=getid(x-1,yy);for(int j=0;j<=19;j++){update(id,j,z);z>>=1;}}for(int i=n;i>=1;i--){for(int j=m-1;j>=1;j--){id[0]=getid(i,j),id[1]=getid(i,j+1);for(int k=0;k<=1;k++){for(z=0;z<=19;z++){v1[k][z][id[0]]+=v1[k][z][id[1]];}}}}for(int i=m;i>=1;i--){for(int j=n-1;j>=1;j--){id[0]=getid(j,i),id[1]=getid(j+1,i);For(k,0,1){for(z=0;z<=19;z++){v1[k][z][id[0]]+=v1[k][z][id[1]];}}}}int ans=0;For(i,1,n){For(j,1,m){id[0]=getid(i,j);for(int i=0;i<=19;i++){if(v1[!(v[id[0]]&(1<<i))][i][id[0]]>0){ans++;break;}}}}cout<<ans<<"\n";return 0;
}
二维树状数组暴力
这种做法是先将所有农药都洒了，对于每次操作(x1,y1,x2,y2,k)，通过树状数组区间修改，将对应区域都加1。
然后枚举植物种类，枚举时，先减去所有该种农药的影响——即对于每次该种操作，对应区域减1。此时已经不存在同种农药了，再枚举该种植物的位置，其中不为0的显然受到了别的农药的影响，因此可判定死亡。
枚举完每一种植物位置后，别忘了把影响加回去。
当然，这样处理还需要按植物的种类存储好位置，并按农药的种类存储好操作。
时间复杂度O(n*m*log(n)*log(m))，log(n)*log(m)来自二维树状数组
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define m_p make_pair
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ls (root<<1)
#define rs ((root<<1)|1)
const int M=1e6+5;
const db eps=1e-8;
const int INF=0x3f3f3f3f;
const int mod=1e7;
struct FastIO//输入挂
{static const int S=200;int wpos;char wbuf[S];FastIO():wpos(0){}inline int xchar(){static char buf[S];static int len=0,pos=0;if(pos==len) pos=0,len=fread(buf,1,S,stdin);if(pos==len) exit(0);return buf[pos++];}inline int read(){int s=1,c=xchar(),x=0;while(c<=32) c=xchar();if(c=='-') s=-1,c=xchar();for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';return x*s;}~FastIO(){if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;}
}io;
int t,n,m,c[M];
int getid(int x,int y){return (x-1)*m+y;
}
struct node{int x,y;node(int _x=0,int _y=0):x(_x),y(_y){}
};
struct node1{int x,y,xx,yy;node1(int _x=0,int _y=0,int _xx=0,int _yy=0):x(_x),y(_y),xx(_xx),yy(_yy){}
};
vector<node> v[M];
vector<node1> v1[M];
int lowbit(int x){return x&(-x);
}
void add(int x,int y,int z){if(x<=0||y<=0) return;int tmpy=y;while(x<=n){y=tmpy;while(y<=m){c[getid(x,y)]+=z;y+=lowbit(y);}x+=lowbit(x);}
}
int sum(int x,int y){int res=0,tmpy=y;while(x>0){y=tmpy;while(y>0){res+=c[getid(x,y)];y-=lowbit(y);}x-=lowbit(x);}return res;
}
void update(int x,int y,int xx,int yy,int z){add(x,y,z);add(xx+1,yy+1,z);add(xx+1,y,-z);add(x,yy+1,-z);
}
int main(){
// freopen("in.txt","r",stdin);n=io.read(),m=io.read(),t=io.read();int x,y,xx,yy,z,id[4];For(i,1,n){For(j,1,m){z=io.read();v[z].p_b(node(i,j));}}For(i,1,t){x=io.read(),y=io.read(),xx=io.read(),yy=io.read(),z=io.read();v1[z].p_b(node1(x,y,xx,yy));update(x,y,xx,yy,1);}int ans=0;For(i,1,n*m){if(v[i].size()>0){for(node1 tt:v1[i]){update(tt.x,tt.y,tt.xx,tt.yy,-1);}for(node tt:v[i]){if(sum(tt.x,tt.y)>0) ans++;}for(node1 tt:v1[i]){update(tt.x,tt.y,tt.xx,tt.yy,1);}}}cout<<ans<<"\n";return 0;
}