分数: 600 点
问题陈述
给你一个序列 A=(A_1,A_2,\dots,A_N) 长度 N.
回答以下问题 Q 查询。的 i第查询如下:
- 求其中元素的总和 A_{L_i},A_{L_i+1},\dots,A_{R_i} 不大于 X_i.
在这里,您需要在线回答这些疑问。
也就是说,只有在您回答当前查询后才会显示下一个查询。
因此,而不是 i-th 查询本身,您将获得加密的输入 \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.
什么是按位异或?
非负整数的按位异或 A 和 B, A \oplus B,定义如下:- 中的数字 2^k 地点(k \geq 0)的 二进制的 A \oplus B 是 1 如果正好是对应数字之一 A 和 B 是 1,和 0 否则。
约束
- 所有输入值均为整数。
- 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.