二维树状数组真的还挺神奇的，更新也很神奇，比如我要更新一个区域内的和，我们的更新操作是这样的
add(x1,y1,z);
add(x2+1,y2+1,z);
add(x1,y2+1,-z);
add(x2+1,y1,-z);
我们会想为什么和一维的差这么多，我们不妨这样看
add(x1,y1,z);的更新效果
add(x2+1,y2+1,z);的更新效果
那么这个下半区有两个，我们再更新
add(x1,y2+1,-z);的更新效果
add(x2+1,y1,-z);的更新效果
最后用红的去剪掉黄色部分，就是二维数组的区间更新效果
这样就可以区间更新了，并且这样还可以实现区间求和。
回到这道题
我们可以这样实现，把每种花的种类的坐标存下来
再把每种农药撒的对应区间给存下来，并且更新这数状数组区间，即加一（表示这颗花我又撒了一种农药），
最后我们去遍历这种花，把这种农药的影响减去，看这种花是否为0，如果不是0，就表示这颗肯定会死，并且由于我们每次遍历的是同一种的花，所以不存在重复计算（PS：当时我想这种花，被另外的农药浇了3次以上就会在算其他农药的时候重复计算，实际上是没有的，因为我们每次只遍历这种花，这种花遍历后，就不会出现了）
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #define rep(i,j,k) for(int i=j;i<=k;i++) #define inf 0x3f3f3f3f const int MAXN=1e6+9; using namespace std; int n,m,q; struct node{int x1,y1,x2,y2; }; vector<pair<int,int> >point[MAXN];//存花种类所在的位置 vector<node>p[MAXN];//存询问点 vector<int>tree[MAXN];// int lowbit(int x){return x&(-x); } void add(int x,int y,int z){//二位树状数组的维护//cout<<n<<"--"<<m<<endl;for (int i=x;i<=n;i+=lowbit(i)){for (int j=y;j<=m;j+=lowbit(j)){tree[i][j]+=z;}} } void updata(int x1,int y1,int x2,int y2,int z){//二维树状数组的更新操作 add(x1,y1,z);add(x2+1,y2+1,z);add(x1,y2+1,-z);add(x2+1,y1,-z); } int query(int x,int y){int ans=0;for (int i=x;i;i-=lowbit(i)){for(int j=y;j;j-=lowbit(j)){ans+=tree[i][j];}}return ans; } int main(){scanf("%d %d %d",&n,&m,&q);for (int i=1;i<=n;i++)tree[i].resize(m+1);// for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){int z;scanf("%d",&z);point[z].push_back(make_pair(i,j));//把每个种花对于的坐标存起来 }}for (int i=1;i<=q;i++){int x1,x2,y1,y2,k;scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&k);updata(x1,y1,x2,y2,1);//更新二维树状数组树p[k].push_back(node{x1,y1,x2,y2});//把这个农药类型的K更改保持起来 }int ans=0;for (int i=1;i<=n*m;i++){if (point[i].size()>0){for (int j=0;j<p[i].size();j++)updata(p[i][j].x1,p[i][j].y1,p[i][j].x2,p[i][j].y2,-1);//把这种农药的所有更改都删除for (int j=0;j<point[i].size();j++){if (query(point[i][j].first,point[i][j].second))//检查是否含为0,即是否有不是这种类型的更改ans++;}for (int j=0;j<p[i].size();j++)updata(p[i][j].x1,p[i][j].y1,p[i][j].x2,p[i][j].y2,1);//把这种更改删除 }}printf("%d\n",ans);return 0; }
