Solution CF1140F Extending Set of Points

对于一个点集 S ,定义 E(S) 为以下算法的结果: 如果 S 中存在 (x1, y1),(x1, y2),(x2, y1),并且不存在 (x2, y2)(x2,y2),那么把 (x2, y2) 加入点集。 循环这个操作直到不能做为止。 现在让你维护一个点集,支持插入删除,要求每次操作之后算出 E(S) 的大小。 q \leq 3 \times 10^5,\ 1 \leq x, y \leq 3 \times 10^5。 考虑分别将行列建虚点,集合中每个店 (x,y) 就从左边的 x 号点向右边的 y 号点连边,则答案为每个联通块左边点的个数乘以右边点的个数。 加入点可以直接添加到并查集中,用线段树分治维护删除操作。其中并查集需要按秩合并。 时间复杂度 O(n \log^2 n)。 #include<bits/stdc++.h> template<class T> inline Read more…