P4425 [HNOI/AHOI2018] Turntable

Xiao G and Xiao H plan to have a dinner, but to keep things simple, the statement is as follows: There is a turntable with $n$ items arranged in a circle (numbered $1 \sim n$). The $i$-th item appears at time $T_i$. At time $0$, Xiao G can choose any one of the $n$ items; denote it by $s_0$. If at time $i$ he chooses item $s_i$, then at time $i+1$ he can either keep the current item or move to the next item. When $s_i$ equals $n$, the next item is item $1$; otherwise it is item $s_i + 1$. At every time (including time $0$), if the item Xiao G chooses has already appeared, then he will mark it. Xiao H wants to know, under the optimal strategy of choosing items, when can Xiao G mark all items. However, the appearance times of items will be modified from time to time. We describe this as $m$ modifications, each changing the appearance time of one item. After each modification, you must also output the answer for the current state. For some test points, Xiao H also imposes a forced online constraint.

The first line contains three non-negative integers $n$, $m$, and $p$, meaning there are $n$ items and $m$ modifications. The value of $p$ is either $0$ or $1$; when $p = 1$, the problem is forced online; otherwise $p = 0$. The next line contains $n$ non-negative integers. The $i$-th number $T_i$ is the appearance time of item $i$. Each of the next $m$ lines contains two non-negative integers $x$ and $y$, representing one modification and its query. The modification works as follows: 1. If $p = 0$, set the appearance time of item $x$ to $y$, i.e., $T_x \leftarrow y$. 2. If $p = 1$, first XOR $x$ and $y$ with LastAns respectively to obtain $x'$ and $y'$, then set $T_{x'} \leftarrow y'$. Here LastAns is the result of the previous query; in particular, for the first modification, LastAns is the answer for the initial state. It is guaranteed that the input is valid.

Output one integer on the first line, the answer for the initial state. Then output $m$ lines, each containing one integer, the answer after each modification.

【Constraints】 ::cute-table[]{tuack} | Test point id | $n$ | $m$ | $T_i / T_x$ | $p$ | | :-: | :-: | :-: | :-: | :-: | | 1 | $\le 10$ | $\le 10$ | $\le 10$ | $=0$ | | 2 | $\le 1000$ | $=0$ | $\le 1000$ | ^ | | 3 | $\le 100000$ | ^ | $\le 100000$ | ^ | | 4 | $\le 5000$ | $\le 5000$ | ^ | ^ | | 5 | $\le 80000$ | $\le 80000$ | ^ | ^ | | 6 | ^ | ^ | ^ | $=1$ | | 7 | $\le 90000$ | $\le 90000$ | ^ | $=0$ | | 8 | ^ | ^ | ^ | $=1$ | | 9 | $\le 100000$ | $\le 100000$ | ^ | $=0$ | | 10 | ^ | ^ | ^ | $=1$| For all testdata, it is guaranteed that $3 \le n \le 10^5$, $0 \le m \le 10^5$, and $0 \le T_i / T_x \le 10^5$. Translated by ChatGPT 5