xor hashing 真牛逼
题意
一个 \(n*m\) 的网格，有 \(q\) 个操作，每次操作是下列 \(3\) 种之一。
1 r1 c1 r2 c2 表示加入一个定点为 \((r1, c1), (r2, c2)\) 的框。
2 r1 c1 r2 c2 表示删除一个定点为 \((r1, c1), (r2, c2)\) 的框。
3 r1 c1 r2 c2 表示在不经过框的前提下，能否从 \((r1, c1)\) 走到 \((r2, c2)\)。
保证框的边缘不会重叠。
做法
切入点是最后一句话，保证框的边缘不会重叠。
么两个点是联通的就是包含他们的框相同，必要性是显然的，如果点 \(x\) 在一个框里，\(y\) 不在，那么 \(x\) 去 \(y\) 必然要经过这个框。
充分性的话，由于框的边缘不会重叠，定义包含点 \(x\) 的集合为 \(S(x)\)，设两个点 \(x, y\) 满足 \(S(x) = S(y) = S\)，那么 \(S\) 中所有的框的交集显然是联通的，因为这个交集的边缘是由 \(S\) 中的某些框的边缘组成的，则不会有别的东西与他们相交，也就不会把这个交集切开。
然后就是一个技巧，如何快速判断 \(S(x)\) 和 \(S(y)\) 是否相同，我们可以把每个 \(S\) 中的所有框随机一个权值，把整个集合的权值定义为集合中所有框的权值的异或和，直接比较即可。
那么操作就相当于矩形 \(xor\)（操作 1 和 2 本质相同），查两个点的权值是否相同。
这个用二维树状数组即可直接维护。
代码
先鸽。
标签：r1,r2,边缘,Antiquity,Untended,权值,c2,c1,CF869E From： https://www.cnblogs.com/chengchunhao/p/16785849.html