下面的标号都是 0-indexed 的。
有一个 \(N\) 个点的图，一开始没有边。
接下来进行 \(Q\) 次加边操作，每次连接两个点，每次操作后你要回答：计 \(C_i\) 为 \(i\) 号节点所在连通块的点集，你要找到一个长度最小的区间 \([l,r]\) 满足 \(\bigcup_{k=l}^{r} C_k = \{0,1,\ldots,N-1\}\)。
操作强制在线，\(N \le 10^5, Q \le 2 \times 10^5\)。
无
对于每个点，记 \(n_i\) 为最小的 \(j\) 满足 \(i<j\) 且 \(i,j\) 处于同一连通快（不存在的话记为 \(N\)）。
记 \(b_r\) 为最大的 \(l\) 使得 \([l,r]\) 满足条件（不一定存在），那么
考虑怎么快速维护 \(b\)。
在合并联通快时，把点数少的联通快的每个点加到大的那个去（加点次数是 \(O(N \log{N})\) 的）。
考虑加入后新生成的一个间隔 \(x,y(x<y)\) 产生的影响（\(n_i\) 容易维护）。容易发现只有 \(b_r=x\) 的位置可能会变大（并且这是一段连续区间），不妨考虑这段区间中满足 \(n_i>x\) 的第一个 \(i\)，那么 \(i \le r < n_i\) 的 \(b_r\) 都会变成 \(i\)。然后把 \(x\) 改成 \(n_i\)，继续这个操作直到跑出区间。
虽然每次会把一段区间切成若干段（每段的 \(b\) 不同），但是只有区间边界上的新区间有可能和左边/右边的合并，所以复杂度是对的。
路上
原文：https://www.cnblogs.com/iefnah06/p/12657218.html