题意： n*m 的格子，有三种操作， 1、在一个矩形周围加一层障碍。2、把一个矩形周围的障碍去掉。 3、询问两个格子是否可达。 题目保证不会有矩形障碍交叉，且去掉的矩形一定是在前面已给出的。
tags：
知道二维树状数组的话应该很容易想到怎么做，增减矩形只要给矩形里面的格子打上这个矩形的标记，询问的时候就看两个格子的标记是否一样即可。
但这题难在给矩形一个hash值，必须要保证两个被不同矩形围着的格子上标记的hash值不一样，这其实不太可能一定保证，只能让概率尽可能小。
我们可以随机给出矩形的 hash值，具体证明看官方题解。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second #define PII pair<int , int > typedef long long ll; const int N = 2505; ll rd() { return rand()<<15 | rand(); } int n, m, q; ll bit[N][N]; map< pair< PII, PII > , int > mp; void add(int r, int c, int x) { for(int i=r; i<N; i+=i&-i) for(int j=c; j<N; j+=j&-j) bit[i][j] += x; } void update(int r1, int c1, int r2, int c2, int x) { add(r2+1, c2+1, -x); add(r1, c1, -x); add(r1, c2+1, x); add(r2+1, c1, x); } ll Sum(int r, int c) { ll ans = 0; for(int i=r; i; i-=i&-i) for(int j=c; j; j-=j&-j) ans += bit[i][j]; return ans; } int main() { srand(time(0)); rep(i,1,50) srand(rd()); scanf("%d%d%d", &n, &m, &q); int t, r1, c1, r2, c2; rep(i,1,q) { scanf("%d%d%d%d%d", &t, &r1, &c1, &r2, &c2); if(t==1) { int rdm = rd(); update(r1, c1, r2, c2, rdm); mp[MP(MP(r1,c1), MP(r2,c2))] = rdm; } else if(t==2) { int tmp = mp[MP(MP(r1,c1), MP(r2,c2))]; update(r1, c1, r2, c2, -tmp); } else { ll ans1=Sum(r1, c1), ans2=Sum(r2, c2); if(ans1==ans2) puts("Yes"); else puts("No"); } } return 0; }