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+7; const int N = 1e6 + 100; 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 = 0; for(int i = x; i > 0; i -= lowbit(i)) for(int j = y; j > 0; 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 = 0; scanf("%d%d%d", &n, &m, &t); for(int i = 1; i <= n; i++) dp[i].resize(m+10); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d", &v); save[v].pb(pll(i,j)); } } for(int i = 1; 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, 1); Add(A[i].x2+1,A[i].y2+1,1); Add(A[i].x1,A[i].y2+1,-1); Add(A[i].x2+1,A[i].y1,-1); } sort(A+1,A+1+t,cmp); for(int i = 1, j = 1, zz; i <= n * m; i++){ while(A[j].k < i && j <= t) j++; if(save[i].size() == 0) continue; zz = j; while(A[zz].k == i && zz <=t) zz++; for(int z = j; z < zz; ++z){ Add(A[z].x2+1,A[z].y2+1,-1); Add(A[z].x1,A[z].y1,-1); Add(A[z].x1,A[z].y2+1,1); Add(A[z].x2+1,A[z].y1,1); } for(auto it : save[i]){ if(Query(it.fi, it.se)){ ans++; } } for(int z = j; z < zz; ++z){ Add(A[z].x2+1,A[z].y2+1,1); Add(A[z].x1,A[z].y1,1); Add(A[z].x1,A[z].y2+1,-1); Add(A[z].x2+1,A[z].y1,-1); } j = zz; } cout << ans << endl; return 0; }
全部评论
(1) 回帖