4088： Adjacent Swaps

# Adjacent Swaps ### 内存 1024MB ### 时间 2S ## 题目描述 $N$ 个球从左到右排成一行。初始时，从左往右第 $i (1 ≤ i ≤ N)$ 个球上写着整数 $i$。 小高执行了 $Q$ 次操作。第 $i (1 ≤ i ≤ Q) $次操作如下: 将写有整数 $x_i$ 的球与其右侧相邻的球交换。如果写有整数 $x_i$ 的球原本在最右端，则改为与左侧相邻的球交换。 设操作后从左往右第$ i (1 ≤ i ≤ N) $个球上写的整数为 $a_i$。请求出 $a_1,...,a_N$。 ## 输入格式 输入按以下格式从标准输入给出: $N \ Q$ $x_1$ $⋮$ $x_Q$ ## 输出格式 输出 $a_1,...,a_N$，用空格分隔。 ## 输入输出样例 ### 输入样例1 ``` 5 5 1 2 3 4 5 ``` ### 输出样例1 ``` 1 2 3 5 4 ``` ### 输入样例2 ``` 7 7 7 7 7 7 7 7 7 ``` ### 输出样例2 ``` 1 2 3 4 5 7 6 ``` ### 输入样例3 ``` 10 6 1 5 2 9 6 6 ``` ### 输出样例3 ``` 1 2 3 4 5 7 6 8 10 9 ``` ## 数据范围与提示 【样例1说明】 操作过程如下: - 交换写有 $1$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $2,1,3,4,5$。 - 交换写有 $2$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $1,2,3,4,5$。 - 交换写有 $3$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $1,2,4,3,5$。 - 交换写有 $4$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $1,2,3,4,5$。 - 交换写有 $5$ 的球与其左侧相邻的球，因为它在最右端。现在球上的整数从左到右为 $1,2,3,5,4$。 【数据范围】 - $2 ≤ N ≤ 2 × 10^5$ - $1 ≤ Q ≤ 2 × 10^5$ - $1 ≤ x_i ≤ N$ - 所有输入均为整数 ## 题目来源 ABC250C