开心.jpg
J.farm
先解释一下题意，题意就是一个n*m的矩形区域，每个点代表一个植物，然后不同的植物对应不同的适合的肥料k，如果植物被撒上不适合的肥料就会死掉。然后题目将每个点适合的肥料种类(不同的数字代表不同的种类)给出(最多n*m种肥料)，然后T次操作，每次操作都是把以(x1,y1)为左上角,以(x2,y2)为右下角确定的矩形区域撒上种类为k的肥料，问T次操作后，死掉了多少植物。
这个题可以是个经典的二维树状数组的题目，通过二维树状数组维护区间，以及各种神奇操作过了这道题。
这道题有三种姿势可以过。
1)通过二维树状数组维护区间，通过hash随机化，使得点增加的数为初始存入的值的倍数，eg：8=4+4而不是8=2+6，最后直接取模初始值，不是倍数的就说明发生了变化。
2)通过二维树状数组维护变化的区间，然后vector保存不同种类的点的坐标，然后遍历所有种类。
3)大暴力，通过前缀和，变化过的点，下次就不再进行操作，一个点最多暴力两次，具体的不清楚什么姿势过的。
我是用第二种思路写的。
感觉vector真的是个好东西，通过vector把种类划分，就可以很轻松的解决种类划分问题。
二维树状通过四个点维护区间，和差分数组一样都是维护前缀和，本来还想用差分数组乱搞试试，好像没必要，因为这两个东西都是通过L，R左右两个边界维护前缀和，在L处+value，在R处-value，然后最后遍历一遍就可以得到区间的前缀和。具体有关树状数组和差分数组的问题，百度找度娘。
写这个题的思路就是通过一个vector将适合该种类i的点的坐标存起来。然后T次操作，再通过一个vector将撒上种类为k的区间的两个点的坐标存起来。将撒上肥料的区间对应的二维树状数组进行更新操作，每操作一个区间就将该区间的树状数组进行更新。T次操作后，每个点被操作过几次就可以通过树状数组查询出来。
然后遍历1到n*m种肥料，对于每一种肥料，把撒过该种肥料的区间取消标记，然后查询适合该种肥料的点，如果该点对应的树状数组里存的值不为0，说明有其他种类的肥料撒过该点，这个点的植物就死了，计数。然后再把取消的该点的标记变回去，这样不影响其他种类的点。
具体的操作都在代码里写了注释。
对于遍历1到n*m种肥料的时候，通过auto po:points[i]就可以很简洁的遍历vector，这个东西就类似于vector<int>::iterator it，it=points[i].begin();it!=points[i].end();it++;具体的自行百度，反正这个东西就可以把代码变的简洁好看一点。关于vector以及auto，贴几个博客链接:
就这些，贴代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<vector> 8 #include<cstdlib> 9 #include<cctype> 10 using namespace std; 11 const int maxn=1e6+10; 12 const int inf=0x3f3f3f3f; 13 #define pii pair<int,int> 14 15 vector<vector<int> >tree; 16 int n,m; 17 18 void init() 19 { 20 tree.resize(n+1); 21 for(int i=0;i<=n;i++){ 22 tree[i].resize(m+1); 23 } 24 for(int i=0;i<=n;i++){ 25 for(int j=0;j<=m;j++) 26 tree[i][j]=0; 27 } 28 } 29 int lowbit(int x) 30 { 31 return x&(-x); 32 } 33 void add(int x,int y,int val) 34 { 35 for(int i=x;i<=n;i+=lowbit(i)){ 36 for(int j=y;j<=m;j+=lowbit(j)){ 37 tree[i][j]+=val; 38 } 39 } 40 } 41 int query(int x,int y) 42 { 43 int ans=0; 44 for(int i=x;i>0;i-=lowbit(i)){ 45 for(int j=y;j>0;j-=lowbit(j)){ 46 ans+=tree[i][j]; 47 } 48 } 49 return ans; 50 } 51 void change(int x1,int y1,int x2,int y2,int val) 52 { 53 add(x1,y1,val); 54 add(x1,y2+1,-val); 55 add(x2+1,y1,-val); 56 add(x2+1,y2+1,val); 57 } 58 template <class T> 59 inline void scan_d(T &ret) 60 { 61 char c; 62 ret = 0; 63 while ((c = getchar()) < '0' || c > '9'); 64 while (c >= '0' && c <= '9') 65 { 66 ret = ret * 10 + (c - '0'), c = getchar(); 67 } 68 } 69 vector<pii>points[maxn]; 70 vector<pair<pii,pii> >area[maxn]; 71 int main() 72 { 73 int t; 74 scan_d(n);scan_d(m);scan_d(t); 75 init(); 76 for(int i=1;i<=n;i++){ 77 for(int j=1;j<=m;j++){ 78 int kind; 79 scan_d(kind); 80 points[kind].push_back({i,j});//points记录种类为kind的点的坐标 81 } 82 } 83 while(t--){ 84 int x1,y1,x2,y2,k; 85 scan_d(x1);scan_d(y1);scan_d(x2);scan_d(y2);scan_d(k); 86 area[k].push_back({{x1,y1},{x2,y2}});//将修改为k的区间保存 87 change(x1,y1,x2,y2,1);//将修改过的区间存到树状数组里进行维护，每修改过一次就赋值+1 88 } 89 int ans=0; 90 for(int i=1; i<=n*m; i++){//遍历 91 for(auto ar:area[i]){ 92 int x1=ar.first.first; 93 int y1=ar.first.second; 94 int x2=ar.second.first; 95 int y2=ar.second.second; 96 change(x1,y1,x2,y2,-1);//将更改为k的区间还原 97 } 98 for(auto po:points[i]){ 99 int xx=po.first,yy=po.second; 100 int cnt=query(xx,yy); 101 if(cnt!=0)ans++;//如果查询出来的值不为0，说明对于适合种类为i的点来说，有其他种类更改过，所以这个点的要死掉了 102 } 103 for(auto ar:area[i]){//将还原的种类i更改过的区间再变成修改过的样子，这样才不会影响适合其他种类的点 104 int x1=ar.first.first; 105 int y1=ar.first.second; 106 int x2=ar.second.first; 107 int y2=ar.second.second; 108 change(x1,y1,x2,y2,1); 109 } 110 } 111 printf("%d ",ans); 112 return 0; 113 }
就这样，很认真的写的代码和博客。