この問題は，おおまかに以下の方針で解くことができます．

• \(i=1,\dots,N\) に対して，\(S_i\) のサイズを \(a_i\) とし，「\(S_i\) に \(x\) が含まれるなら \(1\), 無いなら \(0\)」を \(b_{i}^{(x)}\) とする．列 \((a_1, \dots, a_N)\)に対して，各ノードで最大値とその個数を管理する遅延セグメント木 \(A\) をもつ．また，\(60\) 個の列 \((b_1^{(x)}, b_N^{(x)})\) に対して，各ノードで AND/OR を管理する遅延セグメント \(B\) をもつ．
• 更新クエリで与えられる更新区間を，\(x\) を含む集合の区間・\(x\) を含まない集合の区間に分割する(これは，\(1\) 回の分割ごとに \(B\) 上で二分探索を行えばよい)．このとき，各小区間において \(a_i, b_i^{(x)}\) がすべて同じ値だけ変動する(追加なら \(+1\), 削除なら \(-1\), 何もしないなら \(0\))．

これが時間計算量 \(O(N + Q \log N)\) を達成することを示します．

遅延セグメント木 \(A, B\) の初期化は \(O(N)\) で可能です．また各更新クエリについては，更新区間が \(k_q\) 個の区間に分割されるとき \(O(k_q \log N)\) で可能です．各取得クエリは \(O(\log N)\) です．よって，\(\sum_q k_q = O(Q)\) であれば計算量が示されます．

\(x\) が \(S_i, S_{i+1}\) の片方のみに属するような \((i, x)\) の組の集合を \(\Phi\) とおきます．初期値は \(\Phi = \empty\) であり，また明らかに \(|\Phi| \geq 0\) が常に成り立ちます．

各更新クエリ \([L, R]\) で，更新区間が \(k_q\) 個の区間に分割されるとすると，\(\Phi\) は以下のように変動します．

• \(i = L, \dots, R-1\) のうちちょうど \(k_q-1\) 個において，\((i, x) \in \Phi\) である．更新後，これら \(k_q-1\) 個の要素が \(\Phi\) から失われる．
• \(\Phi\) に追加され得る要素は \((L-1, x), (R,x)\) の \(2\) 通りである．

よって，\(Q\) 回のクエリにおいて \(\sum_q k_q = O(Q)\) であることがわかり，主張が示されました．