Codeforces 1140F (可撤销并查集+线段树区间划分优化)

Codeforces 1140F
题意:$S$一开始是$\empty$, 现在支持插入一个数/删除一个点,并且这个点一定只会插入一次删除一次,求每次操作完后集合$\text{E}(S)$的大小。$\text{E}(S)$集合一开始是当前的$S$, 如果$(x_1,y_1) \in \text{E}(S), (x_1,y_2) \in \text{E}(S), (x_2,y_1) \in \text{E}(S), (x_2,y_2) \notin \text{E}(S)$,那么$(x_2,y_2)$被加入到$\text{E}(S)$中,一直操作直到没有为止。

这题类似 CF 某场 EJOI 的题,我们发现将$(x,y)$看做连边,则答案就是一个联通块的$x,y$值域之积。

然后我们就可以维护并查集,但是这里有删除,我们联想到可撤销并查集

但是并不好用,因为一个数对有效范围是一个区间

所以我们想到用线段树来优化($\log$级优化),类比于线段树优化连边

即我们开一棵线段树,把每个数对有效区间在线段树上打好标记,然后我们可以按$\text{dfs}$序来遍历线段树,每次遍历到线段树的一个区间,暴力插入当前区间上所有有标记的数对,然后之后退出这个点再暴力删掉。由于线段树上一个大区间会被分成$\log$级别的小区间,然后每个修改最多操作$\log n$次,那么就符合时间复杂度了。

这种线段树优化的方法很好,以后一些整区间的优化可以联想到线段树划分区间来优化,其实和线段树优化连边思路有相似点,都是利用线段树上一个大区间会被分成$\log$级别的小区间来优化复杂度。

------ 本文结束 ------