牛客第二场-J-farm-二维树状数组

  二维树状数组真的还挺神奇的，更新也很神奇，比如我要更新一个区域内的和，我们的更新操作是这样的

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;
}