\(q=1\) で \(L\) が奇数かつ \(R\) が偶数のときの構成方法の別解です。
条件を満たす集合の要素数が \(\frac{R-L+1}{2}\) か \(\frac{R-L+3}{2}\) であることまでは考察できているものとします。
\(L,L+1,\dots,R\) に対応する \(R-L+1\) 個の頂点を用意し、\(2\) 進数表記でちょうど \(1\) 桁異なるような \(2\) 頂点間に辺を張ります。
このグラフは、辺数が \(O((R-L)\log(R-L))\) の二部グラフであり、求めるものはその最大独立集合です。 二部グラフにおいて最大マッチングから最大独立集合を求める方法はよく知られているため、最大マッチングの構成方法を示します。 \((L+1,L+2),(L+3,L+4), \dots (R-2,R-1)\) をマッチングさせるようにフローを流しておくと、さらに流せる流量は高々 \(1\) です。 残余グラフに対して DFS などを行うことで、\(O((R-L)\log(R-L))\) で最大マッチングを求めることができます。