P8995 [Peking University Training 2021] Random Data

CTT2021 D4T3

There are $n$ items, numbered $0, \cdots, n-1$. The value of item $i$ is defined as $v_i$. A and B take turns playing a game, which consists of multiple rounds. At the start of each round, if all available items have been taken, the game ends immediately. Otherwise, A must choose an untaken item and take it. Suppose the item A takes has index $i$. Next, B may choose one untaken item from item $(i - d + n) \bmod n$ and item $(i + d) \bmod n$ to take, or B may choose to skip this action. Then the game proceeds to the next round. In particular, if both of these items have already been taken, B can only choose to skip. Both A and B want to maximize the sum of values of the items they take. We assume both A and B play optimally. In addition, before the game starts, some items may be unavailable. During the game, unavailable items are ignored, i.e., neither A nor B can take unavailable items. When all available items have been taken, the game ends immediately. Initially, all items are available. Your program needs to support $q$ operations. In each operation, given an $x$: if item $x$ is unavailable, it becomes available; if it is available, it becomes unavailable. After each operation, you need to answer: assuming the game starts from the current state, what is the sum of values of the items taken by B when the game ends. Unfortunately, this is an IO problem: **the number of items may be up to $10^{16}$**. As an OIer, you cannot handle data at such a large scale, so $v_i$ will be generated in a **special way**: given an array $w$ of length $m$, $v_i = w_{i \bmod m}$.

The first line contains four **positive integers** $n, d, m, q$, with $1 < n \le 10^{16}, 1 \le d < n, 1 \le m \le 2 \times 10^4, q \le 10^5$. The second line contains $m$ integers. The $i$-th integer represents the value of $w_{i-1}$, with $1 \le w_i \le 400$. The next $q$ lines each contain an integer $x$, representing an operation on item $x$. It is guaranteed that $0 \le x < n$.

Output $q$ lines, each containing one integer, corresponding to the answer after each operation.

Subtask 1 (5 pts): $n \le 20, q = 1$. Subtask 2 (10 pts): $n \le 10^5, q = 1$. Subtask 3 (15 pts): $n, q \le 10^5$. Subtask 4 (30 pts): $q = 1$. Subtask 5 (40 pts): No special constraints. If needed, you can use `__int128` to handle `long long` multiplication modulo. Below is an example of using `__int128` to compute $a \times b \bmod m$: ```cpp long long a = 1e15; long long b = 1e15; long long m = 12345678910; long long c = ((__int128) a * b) % m; ``` Translated by ChatGPT 5