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

输入 #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

说明/提示

数据范围

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