AT_abc339_g [ABC339G] Smaller Sum

[problemUrl]: https://atcoder.jp/contests/abc339/tasks/abc339_g 長さ $ N $ の数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 以下の $ Q $ 個のクエリに答えてください。このうち $ i $ 個目のクエリは以下の通りです。 - $ A_{L_i},A_{L_i+1},\dots,A_{R_i} $ のうち $ X_i $ 以下であるものの総和を求めよ。 但し、あなたはこのクエリにオンラインで答える必要があります。 「オンラインでクエリに答える」とは、あるクエリへの回答を行った後で次のクエリが判明することを指します。 このため、 $ i $ 個目のクエリの代わりに、このクエリを暗号化した入力 $ \alpha_i,\ \beta_i,\ \gamma_i $ が与えられます。 以下の手順で本来の $ i $ 個目のクエリを復元して回答してください。 - $ B_0=0 $ 、 $ B_i\ = $ ( $ i $ 個目のクエリの答え ) とする。 - このとき、クエリの復号は以下のようにして行うことができる。 - $ L_i\ =\ \alpha_i\ \oplus\ B_{i-1} $ - $ R_i\ =\ \beta_i\ \oplus\ B_{i-1} $ - $ X_i\ =\ \gamma_i\ \oplus\ B_{i-1} $ 但し、 $ x\ \oplus\ y $ は $ x $ と $ y $ とのビット単位 XOR を表します。 ビット単位 XOR とは 非負整数 $ A,\ B $ のビット単位 XOR 、$ 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 $)。

N/A

N/A

### 制約 - 入力は全て整数 - $ 1\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 0\ \le\ A_i\ \le\ 10^9 $ - $ 1\ \le\ Q\ \le\ 2\ \times\ 10^5 $ - 暗号化されたクエリに対して、以下が成立する。 - $ 0\ \le\ \alpha_i,\ \beta_i,\ \gamma_i\ \le\ 10^{18} $ - 復号した後のクエリに対して、以下が成立する。 - $ 1\ \le\ L_i\ \le\ R_i\ \le\ N $ - $ 0\ \le\ X_i\ \le\ 10^9 $ ### Sample Explanation 1 数列は $ A=(2,0,2,4,0,2,0,3) $ です。 この入力には $ 5 $ 個のクエリが含まれます。 - 最初、 $ B_0=0 $ です。 - 最初のクエリは $ \alpha\ =\ 1,\ \beta\ =\ 8,\ \gamma\ =\ 3 $ です。 - 復号すると $ L_i\ =\ \alpha\ \oplus\ B_0\ =\ 1,\ R_i\ =\ \beta\ \oplus\ B_0\ =\ 8,\ X_i\ =\ \gamma\ \oplus\ B_0\ =\ 3 $ となります。 - このクエリに対する答えは $ 9 $ です。これを $ B_1 $ とします。 - 次のクエリは $ \alpha\ =\ 10,\ \beta\ =\ 12,\ \gamma\ =\ 11 $ です。 - 復号すると $ L_i\ =\ \alpha\ \oplus\ B_1\ =\ 3,\ R_i\ =\ \beta\ \oplus\ B_1\ =\ 5,\ X_i\ =\ \gamma\ \oplus\ B_1\ =\ 2 $ となります。 - このクエリに対する答えは $ 2 $ です。これを $ B_2 $ とします。 - 次のクエリは $ \alpha\ =\ 3,\ \beta\ =\ 3,\ \gamma\ =\ 2 $ です。 - 復号すると $ L_i\ =\ \alpha\ \oplus\ B_2\ =\ 1,\ R_i\ =\ \beta\ \oplus\ B_2\ =\ 1,\ X_i\ =\ \gamma\ \oplus\ B_2\ =\ 0 $ となります。 - このクエリに対する答えは $ 0 $ です。これを $ B_3 $ とします。 - 次のクエリは $ \alpha\ =\ 3,\ \beta\ =\ 6,\ \gamma\ =\ 5 $ です。 - 復号すると $ L_i\ =\ \alpha\ \oplus\ B_3\ =\ 3,\ R_i\ =\ \beta\ \oplus\ B_3\ =\ 6,\ X_i\ =\ \gamma\ \oplus\ B_3\ =\ 5 $ となります。 - このクエリに対する答えは $ 8 $ です。これを $ B_4 $ とします。 - 次のクエリは $ \alpha\ =\ 12,\ \beta\ =\ 0,\ \gamma\ =\ 11 $ です。 - 復号すると $ L_i\ =\ \alpha\ \oplus\ B_4\ =\ 4,\ R_i\ =\ \beta\ \oplus\ B_4\ =\ 8,\ X_i\ =\ \gamma\ \oplus\ B_4\ =\ 3 $ となります。 - このクエリに対する答えは $ 5 $ です。これを $ B_5 $ とします。