18牛客多校训练第二场 J farm

题意：一个n×m的农田， 每个小格子都有一种作物， 现在喷t次农药，每次农药覆盖一个矩形， 该矩形里面与农药类型不同的植物都会死掉， 求最后植物的死亡数是多少。

题解：二维树状数组。 每次喷农药的时候将这个覆盖的区间加一。 然后对于[1,n*m]的植物， 先删除同种植物的同种农药对区间的影响， 然后查询该种植物的是否被标记过了 即 该位置的值 > 1, 最后处理完这种植物再把这种植物的农药再加回去.

代码:

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 1e6 + ;

 vector<int> dp[N];

 vector<pll> save[N];

 int n, m;

 int lowbit(int x)

 {

     return x &(-x);

 }

 void Add(int x, int y, int c)

 {

     for(int i = x; i <= n; i += lowbit(i))

         for(int j = y; j <= m; j += lowbit(j))

             dp[i][j] += c;

 }

 int Query(int x, int y)

 {

     int cnt = ;

     for(int i = x; i > ; i -= lowbit(i))

         for(int j = y; j > ; j -= lowbit(j))

            cnt += dp[i][j];

     return cnt;

 }

 struct Node{

     int x1, y1, x2, y2, k;

 }A[N];

 bool cmp(Node &x1, Node &x2){

     return x1.k < x2.k;

 }

 int main()

 {

     int  t, v;

     int ans = ;

     scanf("%d%d%d", &n, &m, &t);

     for(int i = ; i <= n; i++)

         dp[i].resize(m+);

     for(int i = ; i <= n; i++){

         for(int j = ; j <= m; j++){

             scanf("%d", &v);

             save[v].pb(pll(i,j));

         }

     }

     for(int i = ; i <= t; i++){

         scanf("%d%d%d%d%d", &A[i].x1, &A[i].y1 , &A[i].x2, &A[i].y2, &A[i].k);

         Add(A[i].x1, A[i].y1, );

         Add(A[i].x2+,A[i].y2+,);

         Add(A[i].x1,A[i].y2+,-);

         Add(A[i].x2+,A[i].y1,-);

     }

     sort(A+,A++t,cmp);

     for(int i = , j = , zz; i <= n * m; i++){

         while(A[j].k < i && j <= t)   j++;

         if(save[i].size() == ) continue;

         zz = j;

         while(A[zz].k == i && zz <=t) zz++;

         for(int z = j; z < zz; ++z){

             Add(A[z].x2+,A[z].y2+,-);

             Add(A[z].x1,A[z].y1,-);

             Add(A[z].x1,A[z].y2+,);

             Add(A[z].x2+,A[z].y1,);

         }

         for(auto it : save[i]){

             if(Query(it.fi, it.se)){

                 ans++;

             }

         }

         for(int z = j; z < zz; ++z){

             Add(A[z].x2+,A[z].y2+,);

             Add(A[z].x1,A[z].y1,);

             Add(A[z].x1,A[z].y2+,-);

             Add(A[z].x2+,A[z].y1,-);

         }

         j = zz;

     }

     cout << ans << endl;

     return ;

 }