\(3\) つの数 \(a<b<c\) と任意の \(K\) について、\(c-a\leq K\) ならば \(b-a \leq K\) かつ \(c-b \leq K\) です。つまり、\(a\) と \(c\) の間に辺が張られるならば、\(a\) と \(b\)、\(b\) と \(c\) の間にもそれぞれ辺が張られます。よって、辺は\(S\) の元をソートしたときに隣り合う数の間だけで張るとしても連結性は変わりません。

まず、簡単のため、頂点の追加/削除を行う問題ではなく辺の追加/削除を行う次の問題を考えます。

問題：\(N\) 頂点 \(0\) 辺のグラフがある。以下の \(2\) 種類のクエリを処理せよ。

• \(x\) が与えられる。頂点 \(x\) と \(x+1\) を結ぶ辺がなければ追加し、あれば削除する
• 頂点 \(x\) の属する連結成分のサイズを求める

\(A_i\) を、\(i\) と \(i+1\) を結ぶ辺があれば \(1\)、なければ \(0\) と定めます。このとき、2つのクエリは以下のように処理できます。

• 辺の追加/削除クエリは \(A_i\) の値の更新になります。
• 連結成分数を求めるクエリは、まず、頂点 \(x\) がどこまで右側の頂点と連結かを考えます。\(y>x\) が \(x\) と連結であるための必要十分条件は、\(A[x]+\ldots+A[y-1]=y-x\) となることです。このような最大の \(y\) は \(A\) の区間和が高速に求まるならば二分探索により高速に求めることができます。左側についても同様にできます。

以上から、配列 \(A\) を segment tree で管理することでこの問題は解けます。

もとの問題に戻ります。もとの問題は頂点の追加/削除を行いますが、辺の有無だけではなく頂点の有無も管理するような、以下の \(2\) つの配列 \(A,B\) を segment tree を用いて管理することでほとんど同様に解くことができます。

• \(x\) が \(S\) に含まれれば \(A_i=1\)、含まれなければ \(A_i=0\)
  
• \(x\) と”右隣”の要素の間に辺があれば \(B_i=1\)、辺がなければ \(B_i=0\)
  

クエリ先読み＋座標圧縮や、動的 segment tree を用いることで、segment tree のノード数は十分小さく抑えられ、 計算量は \(O(Q\log Q)\) や \(O(Q\log\max x_i)\) となります。