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 Read more…