AT_abc274_h [ABC274Ex] XOR Sum of Arrays

[problemUrl]: https://atcoder.jp/contests/abc274/tasks/abc274_h 長さ $ M $ の非負整数列 $ B=(B_1,B_2,\dots,B_M),\ C=(C_1,C_2,\dots,C_M) $ に対して、$ B $ と $ C $ の **XOR 和** $ S(B,C) $ を長さ $ M $ の非負整数列 $ (B_1\oplus\ C_1,\ B_2\oplus\ C_2,\ ...,\ B_{M}\oplus\ C_{M}) $ として定義します。ここで $ \oplus $ はビットごとの排他的論理和を意味します。 例えば $ B\ =\ (1,\ 2,\ 3),\ C\ =\ (3,\ 5,\ 7) $ のとき $ S(B,\ C)\ =\ (1\oplus\ 3,\ 2\oplus\ 5,\ 3\oplus\ 7)\ =\ (2,\ 7,\ 4) $ です。 非負整数列 $ A\ =\ (A_1,\ A_2,\ \dots,\ A_N) $ が与えられます。$ A $ の $ i $ 番目から $ j $ 番目までの要素からなる $ A $ の連続部分列を $ A(i,\ j) $ と表します。 以下に説明するクエリが $ Q $ 個与えられるので全て処理してください。 各クエリでは $ 1 $ 以上 $ N $ 以下の整数 $ a,\ b,\ c,\ d,\ e,\ f $ が与えられます。これらの整数は $ a\ \leq\ b,\ c\ \leq\ d,\ e\ \leq\ f,\ b-a=d-c $ を満たします。このとき、$ S(A(a,\ b),\ A(c,\ d)) $ が $ A(e,\ f) $ よりも辞書順で**真に**小さければ `Yes` を、そうでなければ `No` を出力してください。 ビットごとの排他的論理和とは？整数 $ A,\ B $ のビットごとの排他的論理和 $ A\ \oplus\ B $ は、以下のように定義されます。 - $ A\ \oplus\ B $ を二進表記した際の $ 2^k $ ($ k\ \geq\ 0 $) の位の数は、$ A,\ B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。 例えば、$ 3\ \oplus\ 5\ =\ 6 $ となります (二進表記すると: $ 011\ \oplus\ 101\ =\ 110 $)。 数列の辞書順とは？数列 $ A\ =\ (A_1,\ \ldots,\ A_{|A|}) $ が $ B\ =\ (B_1,\ \ldots,\ B_{|B|}) $ より**辞書順で真に小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 1. $ |A|\ かつ\ (A_{1},\ldots,A_{|A|})\ =\ (B_1,\ldots,B_{|A|}) $ である。 2. ある整数 $ 1\leq\ i\leq\ \min\{|A|,|B|\} $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ (A_{1},\ldots,A_{i-1})\ =\ (B_1,\ldots,B_{i-1}) $ - $ A_i $

入力は以下の形式で標準入力から与えられる。ここで $ \text{query}_i $ は $ i $ 番目のクエリを意味する。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ クエリは次の形式で与えられる。 > $ a $ $ b $ $ c $ $ d $ $ e $ $ f $

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリへの答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 0\ \leq\ A_i\ \leq\ 10^{18} $ - $ 1\ \leq\ Q\ \leq\ 5\ \times\ 10^4 $ - $ 1\ \leq\ a\ \leq\ b\ \leq\ N $ - $ 1\ \leq\ c\ \leq\ d\ \leq\ N $ - $ 1\ \leq\ e\ \leq\ f\ \leq\ N $ - $ b\ -\ a\ =\ d\ -\ c $ - 入力される値はすべて整数 ### Sample Explanation 1 $ 1 $ 番目のクエリについて、$ A(1,\ 3)\ =\ (1,\ 2,\ 3),\ A(2,\ 4)\ =\ (2,\ 3,\ 1) $ なので $ S(A(1,3),A(2,4))\ =\ (1\ \oplus\ 2,\ 2\ \oplus\ 3,\ 3\ \oplus\ 1)\ =\ (3,\ 1,\ 2) $ です。これは $ A(1,\ 4)\ =\ (1,\ 2,\ 3,\ 1) $ よりも辞書順で大きいので答えは `No` になります。 $ 2 $ 番目のクエリについて、$ S(A(1,2),A(2,3))\ =\ (3,\ 1) $, $ A(3,4)\ =\ (3,\ 1) $ であり両者は等しく、答えは `No` になります。