CF1578 [B]

· · 个人记录

每次要连的这条弦截出的优弧、劣弧中必有至少一条不跨过 n \to 1，不妨直接找到这段区间里所有出边终点不在这段弧里的点所在集合，然后把它们全部和当前集合合并。

那么因为不跨过 n \to 1，终点如果不在这段弧 [l,r] 里，只可能在 [1,l-1] \bigcup [r+1,n] 中，于是你只需要对每个点维护出边终点的最小值和最大值就可以判断了。

考虑如何进行合并，用线段树维护，每个点上有一个颜色，如果子树 u 中所有叶子全部被合并到了 x 集合，那么 val_u = x，否则 val_u = 0（也就是说如果 val[lc] = val[rc] \ne 0 就把 val 设为 val[lc]），同时维护区间 集合 出边终点的最值，每次暴力递归，如果子树出边终点全都在这段区间就可以 return 了，否则如果遇到 val_u \ne 0，说明这棵子树所在集合是需要合并的，直接合并 val_u 和 now，并且把 val_u 设为 now 即可。

你说得对，但是连续段是 O(n) 的（

考虑如何维护连通块信息使得线段树上面每次每个要合并的集合只被取出来 O(1) 个点：

若把一个连通块的边全部删除，把内部的点按在环上的顺序相邻点连边，这样在判断边相交时是等价于原来的连通块的。

那每次递归时找的就是区间内 pre \in [1,l] 或 suf \in [r,n] 的点对应的集合，这样每个集合至多前后两个点被找出来，复杂度才是对的。

现在的问题是维护 pre 和 suf，这个是不是可以启发式合并啊（，对于小的集合每个元素在大的集合的 set 里找前驱后继然后在线段树上更新。（同时也需要在线段树上更新前驱后继的信息）这样做是 O(n \log^2 n) 的，并查集的复杂度没有乘 \log 可以略去（。

？？？

考虑每次只把取出来的点的 pre 和 suf 更新一下（，这是为什么捏？考虑 u \in y 在 \textbf{Merge}(x,y) 时没有被更新，那么只有一种可能，就是 u 本来所在的凸包位置处没有和其他凸包发生合并（不可能产生交叉边，因为一旦有交叉边就会被转为凸包边），那么它就不需要被更新。所以你每次只需要把所有关键点暴力排个序然后更新这些点的信息就行了。

这样复杂度就是 O(n \log n)。/ll /ll /ll