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$ 的按位异或（bitwise XOR）。

输入格式

输入通过标准输入给出，格式如下： $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$ 个查询的答案。

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

9
2
0
8
5

提示

所有输入值皆为整数。 $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$给定的序列为 $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$。

标签: AtCoder|abc339G

来源

AtCoder|abc339G