103396: [Atcoder]ABC339 G - Smaller Sum

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Answer the following $Q$ queries. The $i$-th query is as follows:

• Find the sum of the elements among $A_{L_i},A_{L_i+1},\dots,A_{R_i}$ that are not greater than $X_i$.

Here, you need to answer these queries online.
That is, only after you answer the current query is the next query revealed.

For this reason, instead of the $i$-th query itself, you are given encrypted inputs $\alpha_i, \beta_i, \gamma_i$ for the query. Restore the original $i$-th query using the following steps and then answer it.

• Let $B_0=0$ and $B_i =$ (the answer to the $i$-th query).
• Then, the query can be decrypted as follows:
  • $L_i = \alpha_i \oplus B_{i-1}$
  • $R_i = \beta_i \oplus B_{i-1}$
  • $X_i = \gamma_i \oplus B_{i-1}$

Here, $x \oplus y$ denotes the bitwise XOR of $x$ and $y$.

Constraints

• All input values are integers.
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• For the encrypted inputs, the following holds:
  • $0 \le \alpha_i, \beta_i, \gamma_i \le 10^{18}$
• For the decrypted queries, the following holds:
  • $1 \le L_i \le R_i \le N$
  • $0 \le X_i \le 10^9$

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$Q$
$\alpha_1$ $\beta_1$ $\gamma_1$
$\alpha_2$ $\beta_2$ $\gamma_2$
$\vdots$
$\alpha_Q$ $\beta_Q$ $\gamma_Q$

Output

Print $Q$ lines.
The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

8
2 0 2 4 0 2 0 3
5
1 8 3
10 12 11
3 3 2
3 6 5
12 0 11

Sample Output 1

9
2
0
8
5

The given sequence is $A=(2,0,2,4,0,2,0,3)$.
This input contains five queries.

• Initially, $B_0=0$.
• The first query is $\alpha = 1, \beta = 8, \gamma = 3$.
  • After decryption, we get $L_i = \alpha \oplus B_0 = 1, R_i = \beta \oplus B_0 = 8, X_i = \gamma \oplus B_0 = 3$.
  • The answer to this query is $9$. This becomes $B_1$.
• The next query is $\alpha = 10, \beta = 12, \gamma = 11$.
  • After decryption, we get $L_i = \alpha \oplus B_1 = 3, R_i = \beta \oplus B_1 = 5, X_i = \gamma \oplus B_1 = 2$.
  • The answer to this query is $2$. This becomes $B_2$.
• The next query is $\alpha = 3, \beta = 3, \gamma = 2$.
  • After decryption, we get $L_i = \alpha \oplus B_2 = 1, R_i = \beta \oplus B_2 = 1, X_i = \gamma \oplus B_2 = 0$.
  • The answer to this query is $0$. This becomes $B_3$.
• The next query is $\alpha = 3, \beta = 6, \gamma = 5$.
  • After decryption, we get $L_i = \alpha \oplus B_3 = 3, R_i = \beta \oplus B_3 = 6, X_i = \gamma \oplus B_3 = 5$.
  • The answer to this query is $8$. This becomes $B_4$.
• The next query is $\alpha = 12, \beta = 0, \gamma = 11$.
  • After decryption, we get $L_i = \alpha \oplus B_4 = 4, R_i = \beta \oplus B_4 = 8, X_i = \gamma \oplus B_4 = 3$.
  • The answer to this query is $5$. This becomes $B_5$.

问题描述

给你一个长度为 $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$ 的按位异或。

限制条件

• 所有输入值为整数。
• $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$

输入

输入从标准输入以以下格式给出：

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$Q$
$\alpha_1$ $\beta_1$ $\gamma_1$
$\alpha_2$ $\beta_2$ $\gamma_2$
$\vdots$
$\alpha_Q$ $\beta_Q$ $\gamma_Q$

输出

打印 $Q$ 行。
第 $i$ 行应该包含第 $i$ 个查询的回答。

样例输入 1

8
2 0 2 4 0 2 0 3
5
1 8 3
10 12 11
3 3 2
3 6 5
12 0 11

样例输出 1

9
2
0
8
5

给定的序列是 $A=(2,0,2,4,0,2,0,3)$。
此输入包含五个查询。

• 最初，$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$。