非負整数が小さい方から \(n\) 個書かれている時( \(0,1,2,\ldots,n-1\) が書かれている時)、各操作をすると

• 偶数を消す方の操作をすると、非負整数が小さい方から \(\lfloor \frac{n}{2} \rfloor \) 個書かれている状態になります。
• 奇数を消す方の操作をすると、非負整数が小さい方から \(\lfloor \frac{n+1}{2} \rfloor \) 個書かれている状態になります。

前者の操作を操作 \(0\)、後者を操作 \(1\) とします。

さらに、\(k\) 回操作を行った場合、\(i\) 回目の操作が操作 \(0\) ならば \(2^{i-1}\) の位が \(0\)、そうでなければ \(1\) であるような非負整数 \(x\) として、非負整数が小さい方から \(\lfloor \frac{n+x}{2^k} \rfloor\) 個書かれた状態になります。以降、この操作列を操作列 \(x\) と呼びます。

操作回数が \(k\) 回の時、非負整数 \(l,l+1,\ldots,r\) がすべて消される操作列 \(x\) の条件は、\(\lfloor \frac{l+x}{2^k} \rfloor = \lfloor \frac{r+1+x}{2^k} \rfloor\) を満たすことです。そして、この条件を満たす \(x\) は \(l+x\) や \(r+1+x\) が \(2^k\) の位で繰り上がるタイミングを考えると \(1\) または \(2\) 個の区間で表すことが出来ます。本問では \(l,r\) が \(N\) 個与えられますが、すべて消された状態に関しても繰り上がる値で座標圧縮をした上で区間の積集合を求めれば良いです。

以上を念頭に次のような動的計画法を考えます。

• \(\mathrm{dp}_{k,i}\) \(k\) 回操作をして、操作列の値 \(x\) が座標圧縮後 \(i\) 番目の区間にある場合、勝つか負けるか

\(k \geq \lceil \log r_N \rceil\) の場合 \(k\) 回目の操作をした時点で残っている非負整数は \(1\) 個以下のため、上記判定法によってすべて消された状態ならば負け、そうでなければ勝ちと出来ます。これを初期状態とし、\(k\) の降順に \([l,r]\) に対応する区間からは(すべて消された状態で無ければ) \(k+1\) 回目の操作をした結果の \([l,r]\) を含む区間と \([l+2^k, r+2^k]\) を調べることで \(k=0\) の状態からどちらが勝つかを求めることが出来ます(なお、\(k+1\) 回操作をした状態に対する区間として \([l,r]\) や \([l+2^k, r+2^k]\) は存在しないかもしれませんが、各値が \(2^{k+1}\) の位で繰り上がるタイミングを基に座標圧縮をしているため、これらを含む区間の存在は言えます)。

計算量は基本的に \(\mathrm{O}(N \log N \log r_N)\) を想定していますが、座標圧縮後の区間を \(k\) の昇順に基数ソートの要領で求める、\(\mathrm{dp}\) の更新を尺取り法の要領で行う等すると \(\mathrm{O}(N \log r_N)\) となります。