题意:一开始一个n*m的矩形(n,m<2500),q个查询(q<50000),每个查询x,x1,y1,x2,y2
x==1:增加一个矩形(矩形不会交叉) 2:删除一个矩形,3:查询(x1,y1)能否到达(x2,y2)
题解:先考虑不能直接dfs找两个点是否可达,可以判断是否在同一个矩形就可以,每一个矩形一个编号,用树状数组更新,又考虑到会出现重复的数,所以哈希一下
#include <bits/stdc++.h>#define maxn 2510#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;int sum[maxn][maxn];map<array<int ,4>,int>mp;int n,m;void add(int x,int y,int d){for(int i = x ; i <= n ; i += i&(-i))for(int j = y ; j <= m ; j += j&(-j)){sum[i][j] += d;}}int sum_ans(int x,int y){int ans = 0;for(int i = x ; i >= 1 ; i -= i&(-i))for(int j = y ; j >= 1 ; j -= j&(-j)){ans += sum[i][j];}return ans;}void update(int x1,int y1,int x2,int y2, int d){add(x1,y1,d);add(x1,y2+1,-d);add(x2+1,y1,-d);add(x2+1,y2+1,d);}int main(){srand(time(0));int q, x, x1, x2, y1, y2, t;scanf("%d%d%d", &n, &m, &q);for(int i=1;i<=q;i++){scanf("%d%d%d%d%d", &x, &x1, &y1, &x2, &y2);if(x == 1){t = x1*131*131*131+y1*131*131+x2*131+y2;mp[{x1, y1, x2, y2}] = t;update(x1, y1, x2, y2, t);}else if(x == 2){t = mp[{x1, y1, x2, y2}];update(x1, y1, x2, y2, -t);}else{if(sum_ans(x1, y1) == sum_ans(x2, y2)) printf("Yes\n");else printf("No\n");}}return 0;}