For three numbers \(a<b<c\) and any \(K\), if \(c-a\leq K\), then \(b-a \leq K\) and \(c-b \leq K\). Consequently, if there is an edge between \(a\) and \(c\), then there are also edges between \(a\) and \(b\), and \(b\) and \(c\). Thus, one can only add edges between adjacent elements in the sorted \(S\) without changing connectivity.

First, for simplicity, we consider the following version that involves edge addition/removal instead of vertex addition/removal:

Question: there is a graph with \(N\) vertices and \(0\) edges. Consider the following two types of query.

• Given \(x\), add an edge between vertices \(x\) and \(x+1\) if absent, or remove it if present.
• Find the size of the connected component containing vertex \(x\).

Let \(A_i\) be \(1\) if there is an edge between \(i\) and \(i+1\), and \(0\) otherwise. Then the two queries can be processed as follows:

• Addition and deletion of an edge is done by updating \(A_i\).
• Given a query that asks for the number of connective component, first consider how far the connected component containing \(x\) extends to the right. \(y>x\) is connected to \(x\) if and only if \(A[x]+\ldots+A[y-1]=y-x\). The maximum such \(y\) can be found with binary search fast if one can find the segment sum of \(A\) fast. Same applies to the left.

Therefore, the altered question can be solved by managing the array \(A\) in a segment tree.

Get back to the original problem. The original problem asks to add or remove vertices. This can be handled almost in the same way by maintaining the following two arrays \(A\) and \(B\) as segment trees in order to manage the existence of vertices as well as edges:

• \(A_i=1\) if \(x\) is contained in \(S\), and \(A_i=0\) otherwise.
  
• \(B_i=1\) if there is an edge between \(x\) and “the next vertex to the right,” and \(B_i=0\) otherwise.
  

By preloading the queries and applying coordinate compression, or using a dynamic segment tree, the number of nodes in the segment trees can be kept small, making the complexity like \(O(Q\log Q)\) or \(O(Q\log\max x_i)\).