P15283 [MCO 2024] Knights

There are $N$ knights labeled $1$ to $N$ standing in a row. The $i$-th knight has power $P_i$. The knights are competing in a jousting tournament. To do so, each knight will hold a sword pointing either to the left or to the right. The $i$-th knight will point their sword to the left if $S_i=0$ and to the right if $S_i=1$ where $S$ is a binary string of length $N$. A joust is defined as the following process: 1. Initially all knights are alive. 2. Let $A$ be the list of knights still alive arranged in increasing order of label and $m$ be the size of $A$. 3. For each $i$ from $1$ to $m$. If the $A_i$-th knight has an adjacent knight with bigger power pointing their sword at the $A_i$-th knight's direction, then mark the $A_i$ knight as $\textbf{dead.}$ Formally the $A_i$-th knight will be marked as dead if one of the following condition is true. - $i-1 > 0$ and $P_{A_{i-1}} > P_{A_{i}}$ and $S_{A_{i-1}} = 1$ - $i+1 \leq m$ and $P_{A_{i+1}} > P_{A_{i}}$ and $S_{A_{i+1}} = 0$ 4. Return to step 2 if there is at least one knight in $A$ marked as dead. Now you are given $Q$ queries, each query are of the form: - Given integer $x$ ($1 \leq x \leq n$), change $S_x$ to $1-S_x$. After each query, find the number of knights alive after a joust is performed. Do note that knights do not stay dead after a joust.

The first line contains two space-separated integers $N$ and $Q$ ($1 \le N,Q\le 10^6$) -- the size of $P$ and the number of queries. The second line contains $N$ space-separated integers $P_1, P_2, \ldots, P_n$ ($1 \le P_i \le N$). The third line contains a binary string $S$ of length $N$. Then $Q$ lines follow. Each of the $Q$ lines contains a single integer $x$ ($1 \le x \le N$) denoting a query to change $S_x$ to $1-S_x$.

Output $Q$ integers $q_1, q_2, \ldots, q_n$ in order on $Q$ lines, where $q_i$ is the number of knights alive after performing a joust after the $i$-th query.

### Note In the first sample input, after the first query, $S$ becomes 01011. Initially, the (labels of) the knights alive are $\{1, 2, 3, 4, 5\}$. After one iteration, the knights remaining are $\{1,3,4\}$. After the second iteration, the knights remaining are $\{3, 4\}$. After the third iteration, no new knight dies, so 2 knights remain after a joust. After the second query, $S$ becomes 01111. After one iteration, the knights remaining are $\{2,3,4,5\}$. After the second iteration, no new knight dies, so 4 knights remain after a joust. ### Scoring Subtask 1 (6 points): $N,Q\le 500$ Subtask 2 (9 points): $P_i \leq P_{i+1}$ for $ 1 \leq i < N$ Subtask 3 (17 points): $P_i \neq P_j$ if $i \neq j$ and the answer for each query is guaranteed to be at most $50$. Subtask 4 (19 points): $P_i \neq P_j$ if $i \neq j$ Subtask 5 (19 points): $N,Q \leq 10000$ Subtask 6 (30 points): No additional constraints