まず、次のことが言えます。

• \(1\) 度ひっくり返された駒は、もうひっくり返せないとしても良い

ここから、次のことも言えます。

• \(i + 2 = j\) となるような \(i, j\) だけしか選べないとしても良い

\(f(l, r)\) を、区間 \([l, r]\) の質問の答えとしましょう。求めたいのは \(f(L_1, R_1), f(L_2, R_2), \ldots, f(L_Q, R_Q)\) です。

さらに、 \(g(l, r) := (f(l, r), f(l + 1, r), f(l, r - 1), f(l + 1, r - 1))\) としましょう。

大事なのは、 \(g(l, m - 1), g(m, r), B, W\) から \(g(l, r)\) が計算できるということです。

よって、この問題はセグメント木を使うことで、 \(\Theta(N + Q \log N)\) 時間で解けます。