P15283 [MCO 2024] Knights

有 $N$ 个骑士，编号 $1$ 到 $N$，站成一排。第 $i$ 个骑士的力量为 $P_i$。 骑士们正在参加一场马上枪术锦标赛。为此，每个骑士需要将他的剑指向左侧或右侧。若 $S_i = 0$，则第 $i$ 个骑士将剑指向左侧；若 $S_i = 1$，则指向右侧。其中 $S$ 是一个长度为 $N$ 的二进制字符串。 一场 **枪术对决** 定义为如下过程： 1. 初始时所有骑士均存活。 2. 令 $A$ 为按编号升序排列的仍存活骑士的列表，$m$ 为 $A$ 的大小。 3. 对于 $i$ 从 $1$ 到 $m$，如果第 $A_i$ 号骑士存在一个 **力量更大** 的相邻骑士，且该相邻骑士的剑尖指向第 $A_i$ 号骑士的方向，则将第 $A_i$ 号骑士标记为 **死亡**。形式化地，若满足以下任一条件，则第 $A_i$ 号骑士将被标记为死亡： - $i-1 > 0$ 且 $P_{A_{i-1}} > P_{A_{i}}$ 且 $S_{A_{i-1}} = 1$ - $i+1 \leq m$ 且 $P_{A_{i+1}} > P_{A_{i}}$ 且 $S_{A_{i+1}} = 0$ 4. 如果列表 $A$ 中至少有一个骑士被标记为死亡，则返回步骤 2。 现在，你将收到 $Q$ 个询问，每个询问的形式如下： - 给定整数 $x$ （$1 \leq x \leq n$），将 $S_x$ 变为 $1-S_x$。 在每次询问之后，请计算经过一场枪术对决后，仍存活的骑士数量。 注意，**骑士不会在上一场对决中死亡后继续死亡**（即每次对决都是独立的，初始状态均为所有骑士存活）。

第一行包含两个以空格分隔的整数 $N$ 和 $Q$ （$1 \le N, Q \le 10^6$）—— 表示数组 $P$ 的长度和询问的数量。 第二行包含 $N$ 个以空格分隔的整数 $P_1, P_2, \ldots, P_n$ （$1 \le P_i \le N$）。 第三行包含一个长度为 $N$ 的二进制字符串 $S$。 接下来 $Q$ 行，每行包含一个整数 $x$ （$1 \le x \le N$），表示将 $S_x$ 变为 $1-S_x$ 的询问。

按顺序输出 $Q$ 行，每行一个整数 $q_i$，其中 $q_i$ 表示在第 $i$ 次询问之后，执行一场枪术对决后仍存活的骑士数量。

#### 注释 在第一个样例输入中，第一次询问后，$S$ 变为 01011。 初始时，存活骑士（的编号）为 $\{1, 2, 3, 4, 5\}$。经过第一轮迭代后，剩余的骑士为 $\{1,3,4\}$。经过第二轮迭代后，剩余的骑士为 $\{3, 4\}$。经过第三轮迭代后，没有新的骑士死亡，因此一场枪术对决后剩余 2 名骑士。 第二次询问后，$S$ 变为 01111。 经过第一轮迭代后，剩余的骑士为 $\{2,3,4,5\}$。经过第二轮迭代后，没有新的骑士死亡，因此一场枪术对决后剩余 4 名骑士。 #### 计分 **子任务 1** （$6$ 分）： $N, Q \le 500$ **子任务 2** （$9$ 分）： 对于 $1 \le i < N$，有 $P_i \leq P_{i+1}$ **子任务 3** （$17$ 分）： 若 $i \neq j$，则 $P_i \neq P_j$，且保证每个询问的答案不超过 $50$ **子任务 4** （$19$ 分）： 若 $i \neq j$，则 $P_i \neq P_j$ **子任务 5** （$19$ 分）： $N, Q \leq 10000$ **子任务 6** （$30$ 分）： 无额外限制 翻译由 DeepSeek 完成