存在初始为空的点集 \(S\), 进行 \(n\) 次操作, 形如:
- \(1\ \ u:\) 若 \(u \in S\) 则令 \(u \notin S\), 否则令 \(u \in S\).
- \(2\ \ u:\) 对 \(S\) 中的结点连无向边, \(x, y\) 之间有边当且仅当 \(|x - y| \leqslant k\). 求 \(u\) 所在的连通块大小.
\(n \leqslant 2 \times 10^{5}, k, u \leqslant 10^{18}\).
对于一个固定的点集 \(S\), 在只需要维护连通块的情况下对所有点对两两判断是否需要连边是没有必要的, 注意到 \(\forall a, b, c \in S(a \leqslant b \leqslant c)\), 若 \(|a - c| \leqslant k\), 则 \(|a - b|, |b - c| \leqslant k\), 所以只对 \(a, b\) 和 \(b, c\) 连边同样可以维护 \(a, b, c\) 两两之间的连通性, 此时边数降到与 \(|S|\) 同阶.
有了上面的结论, 加点是简单的, 只需要求出 \(u\) 在 \(S\) 中的前驱和后继, 判断它们与 \(u\) 是否满足连边条件即可. 连通性用并查集维护, 单次加点的时间复杂度为 \(\log n\).
而对于删点, 我们希望尽可能避免它, 于是求出每个点存在的时间段 \([l, r]\), 将其挂在线段树上覆盖了 \([l, r]\) 的结点上. 遍历线段树时进入结点则加, 退出结点则减, 容易发现这样做只需要处理叶的撤销, 是简单的. 于是我们 \(\Theta(n\log^{2} n)\) 求出了每个时刻询问的答案.
