103396: [Atcoder]ABC339 G - Smaller Sum

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score: $600$ points

Problem Statement

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.

Answer the following $Q$ queries. The $i$-th query is as follows:

  • Find the sum of the elements among $A_{L_i},A_{L_i+1},\dots,A_{R_i}$ that are not greater than $X_i$.

Here, you need to answer these queries online.
That is, only after you answer the current query is the next query revealed.

For this reason, instead of the $i$-th query itself, you are given encrypted inputs $\alpha_i, \beta_i, \gamma_i$ for the query. Restore the original $i$-th query using the following steps and then answer it.

  • Let $B_0=0$ and $B_i =$ (the answer to the $i$-th query).
  • Then, the query can be decrypted as follows:
    • $L_i = \alpha_i \oplus B_{i-1}$
    • $R_i = \beta_i \oplus B_{i-1}$
    • $X_i = \gamma_i \oplus B_{i-1}$

Here, $x \oplus y$ denotes the bitwise XOR of $x$ and $y$.

What is bitwise XOR? The bitwise XOR of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows:
  • The digit in the $2^k$ place ($k \geq 0$) of $A \oplus B$ in binary is $1$ if exactly one of the corresponding digits of $A$ and $B$ in binary is $1$, and $0$ otherwise.
For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

Constraints

  • All input values are integers.
  • $1 \le N \le 2 \times 10^5$
  • $0 \le A_i \le 10^9$
  • $1 \le Q \le 2 \times 10^5$
  • For the encrypted inputs, the following holds:
    • $0 \le \alpha_i, \beta_i, \gamma_i \le 10^{18}$
  • For the decrypted queries, the following holds:
    • $1 \le L_i \le R_i \le N$
    • $0 \le X_i \le 10^9$

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines.
The $i$-th line should contain the answer to the $i$-th query.


Sample Input 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

Sample Output 1

9
2
0
8
5

The given sequence is $A=(2,0,2,4,0,2,0,3)$.
This input contains five queries.

  • Initially, $B_0=0$.
  • The first query is $\alpha = 1, \beta = 8, \gamma = 3$.
    • After decryption, we get $L_i = \alpha \oplus B_0 = 1, R_i = \beta \oplus B_0 = 8, X_i = \gamma \oplus B_0 = 3$.
    • The answer to this query is $9$. This becomes $B_1$.
  • The next query is $\alpha = 10, \beta = 12, \gamma = 11$.
    • After decryption, we get $L_i = \alpha \oplus B_1 = 3, R_i = \beta \oplus B_1 = 5, X_i = \gamma \oplus B_1 = 2$.
    • The answer to this query is $2$. This becomes $B_2$.
  • The next query is $\alpha = 3, \beta = 3, \gamma = 2$.
    • After decryption, we get $L_i = \alpha \oplus B_2 = 1, R_i = \beta \oplus B_2 = 1, X_i = \gamma \oplus B_2 = 0$.
    • The answer to this query is $0$. This becomes $B_3$.
  • The next query is $\alpha = 3, \beta = 6, \gamma = 5$.
    • After decryption, we get $L_i = \alpha \oplus B_3 = 3, R_i = \beta \oplus B_3 = 6, X_i = \gamma \oplus B_3 = 5$.
    • The answer to this query is $8$. This becomes $B_4$.
  • The next query is $\alpha = 12, \beta = 0, \gamma = 11$.
    • After decryption, we get $L_i = \alpha \oplus B_4 = 4, R_i = \beta \oplus B_4 = 8, X_i = \gamma \oplus B_4 = 3$.
    • The answer to this query is $5$. This becomes $B_5$.

Input

Output

得分:600分

问题描述

给你一个长度为 $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$ 的按位异或。

什么是按位异或? 非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下:
  • 二进制表示中 $A \oplus B$ 的第 $2^k$ 位($k \geq 0$)为 $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$。

加入题单

上一题 下一题 算法标签: