← 返回题目列表

AtCoder · abc339_g

G. 较小的总和

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).

约束

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