\(0 \le i \le j \le N\) について、 \(X_i\) の偶奇を決定すると、ある定数 \(C^{\mathrm{even}}_{i,j},C^{\mathrm{odd}}_{i,j}\) を用いて、

• \(X_i\) が偶数の時: \(X_i \oplus C^{\mathrm{even}}_{i,j} = X_j\)
• \(X_i\) が奇数の時: \(X_i \oplus C^{\mathrm{odd}}_{i,j} = X_j\)

と \(X_j\) を \(X_i\) の式で表せます。

クエリごとに \(X_0 = C^{\mathrm{even}}_{0,N} \oplus Y\) と \(X_0 = C^{\mathrm{odd}}_{0,N} \oplus Y\) それぞれが偶奇の条件に整合するか確認し、適切なものを出力すれば良いです。

この \(C^{\mathrm{even}}_{i,j},C^{\mathrm{odd}}_{i,j}\) はSegment Treeを用いて高速に計算できます。

具体的な方法

• 漸化式より、 \(C^{\mathrm{odd}}_{i-1,i}=A_i,C^{\mathrm{even}}_{i-1,i}=B_i\) です。
• \(C^{\mathrm{odd}}_{l,m},C^{\mathrm{even}}_{l,m},C^{\mathrm{odd}}_{m,r},C^{\mathrm{even}}_{m,r}\) がわかっているとき、次のようにして \(C^{\mathrm{odd}}_{l,r},C^{\mathrm{even}}_{l,r}\) を計算できます。
  • \(C^{\mathrm{odd}}_{l,m}\) が奇数のとき
    • \(X_m = X_l \oplus C^{\mathrm{odd}}_{l,m}\) は偶数となる
    • このとき \(X_r = X_m \oplus C^{\mathrm{even}}_{m,r} = X_l \oplus C^{\mathrm{odd}}_{l,m} \oplus C^{\mathrm{even}}_{m,r}\)
    • つまり、\(C^{\mathrm{odd}}_{l,r} = C^{\mathrm{odd}}_{l,m} \oplus C^{\mathrm{even}}_{m,r}\)
  • \(C^{\mathrm{odd}}_{l,m}\) が偶数のとき
    • \(X_m = X_l \oplus C^{\mathrm{odd}}_{l,m}\) は奇数となる
    • このとき \(X_r = X_m \oplus C^{\mathrm{even}}_{m,r} = X_l \oplus C^{\mathrm{odd}}_{l,m} \oplus C^{\mathrm{odd}}_{m,r}\)
    • つまり、\(C^{\mathrm{odd}}_{l,r} = C^{\mathrm{odd}}_{l,m} \oplus C^{\mathrm{odd}}_{m,r}\)
  • \(C^{\mathrm{even}}_{l,m}\) についても偶奇で場合分けをすることで \(C^{\mathrm{even}}_{l,r}\) を計算できる
• \(0\)が単位元の役割を果たします。

クエリあたり時間計算量 \(O(\log N)\) で解くことができます。