AT_abc279_e [ABC279E] Cheating Amidakuji

题目描述

有一个由 $N$ 根竖直的棍子和 $M$ 根连接这些棍子之间的横杆组成的“阿弥陀签”。每根横杆都垂直于竖棍，并且它们的高度各不相同。将竖棍从左到右依次编号为 $1,2,\dots,N$，横杆从上到下依次编号为 $1,2,\dots,M$。横杆 $i\ (1\leq i\leq M)$ 连接了竖棍 $A_i$ 和竖棍 $A_i+1$ 之间。

从竖棍 $1$ 的顶端开始，沿着阿弥陀签向下走，最终到达的竖棍编号称为得分。

对于 $i=1,2,\dots,M$，请回答以下问题：

• 定义 $S_i$ 为将横杆 $i$ 删除后的得分。请计算 $S_i$。

注意，实际上横杆不会真的被删除，因此每个问题是独立的。

更严格地说，具体操作如下：

给定一个长度为 $M$ 的数列 $A=(A_1,A_2,\dots,A_M)$，其中每个 $A_i$ 是 $1$ 到 $N-1$ 之间的整数。对于 $i=1,2,\dots,M$，请回答以下问题：

• 有一个数列 $B=(B_1,B_2,\dots,B_N)$，初始时对于每个 $j$，都有 $B_j=j$。接下来，依次对 $k=1,2,\dots,i-1,i+1,\dots,M$（即除了 $i$ 以外的 $1$ 到 $M$ 的整数 $k$，按升序）进行如下操作：
  • 交换 $B_{A_k}$ 和 $B_{A_k+1}$ 的值。
• 所有操作结束后，满足 $B_j=1$ 的 $j$ 的值即为 $S_i$。请计算 $S_i$。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$

输出格式

输出 $M$ 行。对于每个 $i\ (1\leq i\leq M)$，第 $i$ 行输出 $S_i$ 的值（整数）。

输入输出样例 #1

输入 #1

5 4
1 2 3 2

输出 #1

1
3
2
4

输入输出样例 #2

输入 #2

3 3
2 2 2

输出 #2

1
1
1

输入输出样例 #3

输入 #3

10 10
1 1 1 9 4 4 2 1 3 3

输出 #3

2
2
2
3
3
3
1
3
4
4

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $1\leq A_i\leq N-1\ (1\leq i\leq M)$
• 输入均为整数

样例解释 1

当 $i=2$ 时，$B$ 的变化如下：

• 初始时，$B=(1,2,3,4,5)$
• $k=1$ 时，交换 $B_1$ 和 $B_2$，$B=(2,1,3,4,5)$
• $k=3$ 时，交换 $B_3$ 和 $B_4$，$B=(2,1,4,3,5)$
• $k=4$ 时，交换 $B_2$ 和 $B_3$，$B=(2,4,1,3,5)$

所有操作结束后，$B_3=1$，因此 $S_2=3$。

同理：

• $i=1$ 时：依次对 $k=2,3,4$ 操作后，$B=(1,4,3,2,5)$，所以 $S_1=1$
• $i=3$ 时：依次对 $k=1,2,4$ 操作后，$B=(2,1,3,4,5)$，所以 $S_3=2$
• $i=4$ 时：依次对 $k=1,2,3$ 操作后，$B=(2,3,4,1,5)$，所以 $S_4=4$。

由 ChatGPT 4.1 翻译