AT_abc339_g [ABC339G] Smaller Sum

给定一个长度为 $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$，$A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数，如果 $A,B$ 的该位中只有一个为 $1$，则为 $1$，否则为 $0$。 例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。

输入以如下格式从标准输入读入。 > $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 \leq N \leq 2 \times 10^5$ - $0 \leq A_i \leq 10^9$ - $1 \leq Q \leq 2 \times 10^5$ - 对于加密后的查询，有： - $0 \leq \alpha_i,\ \beta_i,\ \gamma_i \leq 10^{18}$ - 对于解密后的查询，有： - $1 \leq L_i \leq R_i \leq N$ - $0 \leq X_i \leq 10^9$ ### 样例解释 1 数列为 $A=(2,0,2,4,0,2,0,3)$。该输入包含 $5$ 个查询。 - 初始时，$B_0=0$。 - 第一个查询为 $\alpha=1,\ \beta=8,\ \gamma=3$。 - 解密后 $L_1=1,\ R_1=8,\ X_1=3$。 - 该查询的答案为 $9$，记为 $B_1$。 - 下一个查询为 $\alpha=10,\ \beta=12,\ \gamma=11$。 - 解密后 $L_2=3,\ R_2=5,\ X_2=2$。 - 该查询的答案为 $2$，记为 $B_2$。 - 下一个查询为 $\alpha=3,\ \beta=3,\ \gamma=2$。 - 解密后 $L_3=1,\ R_3=1,\ X_3=0$。 - 该查询的答案为 $0$，记为 $B_3$。 - 下一个查询为 $\alpha=3,\ \beta=6,\ \gamma=5$。 - 解密后 $L_4=3,\ R_4=6,\ X_4=5$。 - 该查询的答案为 $8$，记为 $B_4$。 - 下一个查询为 $\alpha=12,\ \beta=0,\ \gamma=11$。 - 解密后 $L_5=4,\ R_5=8,\ X_5=3$。 - 该查询的答案为 $5$，记为 $B_5$。 由 ChatGPT 4.1 翻译