102794: [AtCoder]ABC279 E - Cheating Amidakuji
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:7
Solved:0
Description
Score : $500$ points
Problem Statement
You are given a sequence of length $M$ consisting of integers between $1$ and $N-1$, inclusive: $A=(A_1,A_2,\dots,A_M)$. Answer the following question for $i=1, 2, \dots, M$.
- There is a sequence $B=(B_1,B_2,\dots,B_N)$. Initially, we have $B_j=j$ for each $j$. Let us perform the following operation for $k=1, 2, \dots, i-1, i+1, \dots, M$ in this order (in other words, for integers $k$ between $1$ and $M$ except $i$ in ascending order).
- Swap the values of $B_{A_k}$ and $B_{A_k+1}$.
- After all the operations, let $S_i$ be the value of $j$ such that $B_j=1$. Find $S_i$.
Constraints
- $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)$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$
Output
Print $M$ lines. The $i$-th line $(1\leq i \leq M)$ should contain the value $S_i$ as an integer.
Sample Input 1
5 4 1 2 3 2
Sample Output 1
1 3 2 4
For $i = 2$, the operations change $B$ as follows.
- Initially, $B = (1,2,3,4,5)$.
- Perform the operation for $k=1$. That is, swap the values of $B_1$ and $B_2$, making $B = (2,1,3,4,5)$.
- Perform the operation for $k=3$. That is, swap the values of $B_3$ and $B_4$, making $B = (2,1,4,3,5)$.
- Perform the operation for $k=4$. That is, swap the values of $B_2$ and $B_3$, making $B = (2,4,1,3,5)$.
After all the operations, we have $B_3=1$, so $S_2 = 3$.
Similarly, we have the following.
- For $i=1$: performing the operation for $k=2,3,4$ in this order makes $B=(1,4,3,2,5)$, so $S_1=1$.
- For $i=3$: performing the operation for $k=1,2,4$ in this order makes $B=(2,1,3,4,5)$, so $S_3=2$.
- For $i=4$: performing the operation for $k=1,2,3$ in this order makes $B=(2,3,4,1,5)$, so $S_4=4$.
Sample Input 2
3 3 2 2 2
Sample Output 2
1 1 1
Sample Input 3
10 10 1 1 1 9 4 4 2 1 3 3
Sample Output 3
2 2 2 3 3 3 1 3 4 4
Input
题意翻译
给你两个数组 $A$ 和 $B$,初始时,$B_i=i$。 定义第 $k$ 次操作为 $\operatorname{swap}(B_{A_k},B_{A_k+1})$ 定义 $S_i$ 为依次进行 $1$ 到 $m$ 除 $i$ 号操作外的所有操作后,数字 $1$ 在 $B$ 数组中的位置。 请依次输出 $S_i$ 。Output
得分:$500$分
问题描述
给你一个长度为$M$的序列,包含在$1$到$N-1$之间的整数:$A=(A_1,A_2,\dots,A_M)$。 对$i=1, 2, \dots, M$,回答以下问题。
- 有一个序列$B=(B_1,B_2,\dots,B_N)$。最初,我们有$B_j=j$,对于每个$j$。让我们按照以下顺序为$k=1, 2, \dots, i-1, i+1, \dots, M$执行以下操作(换句话说,按照升序为在$1$到$M$之间的整数$k$)。
- 交换$B_{A_k}$和$B_{A_k+1}$的值。
- 在所有操作之后,让$S_i$为使$B_j=1$的$j$的值。找到$S_i$。
约束条件
- $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)$
- 输入中的所有值都是整数。
输入
输入从标准输入给出以下格式:
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$
输出
打印$M$行。 第$i$行 $(1\leq i \leq M)$ 应包含整数值$S_i$。
样例输入1
5 4 1 2 3 2
样例输出1
1 3 2 4
对于$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$。
样例输入2
3 3 2 2 2
样例输出2
1 1 1
样例输入3
10 10 1 1 1 9 4 4 2 1 3 3
样例输出3
2 2 2 3 3 3 1 3 4 4