https://codeforces.com/contest/869/problem/E
题意:
有 \(n×m\) 个网格,\(x,y\) 表示位于第 \(x\) 行第 \(y\) 列的那个方格。输入 \(x1,y1,x2,y2\),进行三种操作:
操作 1:以 \(x1,y1,x2,y2\) 为对角线的两端可以确定一个矩形(保证 \(x1\le x2,y1\le y2\)),沿着该矩形的外周长造一圈围栏。保证围栏不相交
操作 2:拆除该矩形决定的围栏(保证拆除前存在该围栏)
操作 3:\(x1,y1,x2,y2\) 决定两个点,询问从一个点能否走到另一点
思路:
只有当两个点分别属于的矩形集合完全相同时才能连通。用二维树状数组,在矩形的左上、右下端点加一随机数,在左下、右上端点减去该随机数。加也可换为异或等操作
随机数由 \(x1,y1,x2,y2\) 确定,保证了每个矩形留下的 “痕迹” 是唯一的。不用随机数的话也可用别的线性函数或者其他方法得到一个哈希值,不冲突就行
在矩形的两个端点加 \(d\) ,其他两个端点减 \(d\) 也很巧妙。反正最后两点的前缀和 \(sum\) 相同就代表所在的矩形集合完全相同
#include <iostream> #include <ctime> #include <cstdio> #include <cstdlib> using namespace std; using ll = long long; int n, m, q, op, x1, y1, x2, y2, A, B, C, D; ll tree[2510][2510]; int lowbit(int x) {return x&-x;} void add(int x,int y,ll num) { for(int i=x; i<=n; i+=lowbit(i)) for(int j=y; j<=m; j+=lowbit(j)) tree[i][j]+=num; } ll sum(int x,int y) { ll res=0; for(int i=x; i>=1; i-=lowbit(i)) for(int j=y; j>=1; j-=lowbit(j)) res+=tree[i][j]; return res; } void modify(int sgn) { ll d = ((ll)A*x1+(ll)B*y1+(ll)C*x2+(ll)D*y2) * sgn; add(x1, y1, d); add(x2+1, y2+1, d); add(x1, y2+1, -d); add(x2+1, y1, -d); } void init() { srand(time(0)); A = rand(); B = rand(); C = rand(); D = rand(); } signed main() { init(); cin >> n >> m >> q; while(q--) { scanf("%d%d%d%d%d", &op,&x1,&y1,&x2,&y2); if(op == 1) modify(1); else if(op == 2) modify(-1); else puts(sum(x1,y1) == sum(x2,y2) ? "Yes" : "No"); } return 0; }