P4641 [BJWC2008] Sequence

For a sequence $\{a_n\}$ of length $N$ $(a_i \in [0, 2^{16} - 1])$, perform the following two types of operations, for a total of $M$ operations: 1. `A x` $(x \ge 0)$: $a_i = a_i + x \mod 2^{16}$. 2. `Q i`: Query the value of $Card\{k \mid (a_k\;\&\;2^i) > 0, 1 \le k \le N, k \in \mathbb{Z}\}$. Here, the $\&$ operator is the same as `&` in C/C++ or `and` in Pascal. Given the initial sequence and the list of operations, simulate the process and compute the sum of the results of all `Q` operations.

The first line contains two integers $N, M$ separated by spaces, representing $N$ and $M$. The next $N$ lines each contain one integer, representing the initial sequence. The next $M$ lines each describe one operation, in the format stated in the description.

Output one integer, representing the sum of the results of all `Q` operations.

The initial sequence is $1\;2\;4$. `Q 1`: Only $a_2 = 2$ satisfies $(a_k\;\&\;2^i) > 0$, so the result of this `Q` operation is $1$. `Q 2`: Only $a_3 = 4$ satisfies $(a_k\;\&\;2^i) > 0$, so the result of this `Q` operation is $1$. `A 1`: The original sequence becomes $2\;3\;5$. `Q 1`: Only $a_1 = 2, a_2 = 3$ satisfy $(a_k\;\&\;2^i) > 0$, so the result of this `Q` operation is $2$. `Q 2`: Only $a_3 = 5$ satisfies $(a_k\;\&\;2^i) > 0$, so the result of this `Q` operation is $1$. $1 + 1 + 2 + 1 = 5$, so the final result is $5$. Constraints: $30\%$ of the testdata satisfy $1 \le N \le 100, 1 \le M \le 1000$. $100\%$ of the testdata satisfy $1 \le N, M \le 10^5$. Translated by ChatGPT 5