atcoder#ABC279E. [ABC279E] Cheating Amidakuji

[ABC279E] Cheating Amidakuji

题目描述

$ 1 $ 以上 $ N-1 $ 以下の整数からなる長さ $ M $ の数列 $ A=(A_1,A_2,\dots,A_M) $ が与えられます。 $ i=1,2,\dots,M $ について、以下の質問に答えてください。
  • 数列 B=(B1,B2,,BN) B=(B_1,B_2,\dots,B_N) がある。最初、各 j j について Bj=j B_j=j である。今から、k=1,2,,i1,i+1,,M k=1,2,\dots,i-1,i+1,\dots,M の順に以下の操作を行う (すなわち、i i を除いた 1 1 以上 M M 以下の整数 k k について、昇順に以下の操作を行う)。
    • BAk B_{A_k} BAk+1 B_{A_k+1} の値を入れ替える。
  • 全ての操作が終了した段階で、Bj=1 B_j=1 を満たす j j の値を Si S_i と定義する。Si S_i を求めよ。

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M A1 A_1 A2 A_2 \dots AM A_M

输出格式

M M 行出力せよ。 i (1 i  M) i\ (1\leq\ i\ \leq\ M) 行目には、Si S_i の値を整数として出力せよ。

题目大意

给你两个数组 AABB,初始时,Bi=iB_i=i

定义第 kk 次操作为 swap(BAk,BAk+1)\operatorname{swap}(B_{A_k},B_{A_k+1})

定义 SiS_i 为依次进行 11mmii 号操作外的所有操作后,数字 11BB 数组中的位置。

请依次输出 SiS_i

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

提示

制約

  • 2  N  2× 105 2\ \leq\ N\ \leq\ 2\times\ 10^5
  • 1  M  2× 105 1\ \leq\ M\ \leq\ 2\times\ 10^5
  • 1  Ai  N1 (1 i  M) 1\ \leq\ A_i\ \leq\ N-1\ (1\leq\ i\ \leq\ M)
  • 入力は全て整数

Sample Explanation 1

i = 2 i\ =\ 2 のとき、操作によって B B は以下のように変化します。 - 最初、B = (1,2,3,4,5) B\ =\ (1,2,3,4,5) - k=1 k=1 として操作を行う。すなわち B1 B_1 B2 B_2 の値を入れ替えて、B = (2,1,3,4,5) B\ =\ (2,1,3,4,5) - k=3 k=3 として操作を行う。すなわち B3 B_3 B4 B_4 の値を入れ替えて、B = (2,1,4,3,5) B\ =\ (2,1,4,3,5) - k=4 k=4 として操作を行う。すなわち B2 B_2 B3 B_3 の値を入れ替えて、B = (2,4,1,3,5) B\ =\ (2,4,1,3,5) 全ての操作が終了した段階で B3=1 B_3=1 であるため、S2 = 3 S_2\ =\ 3 です。 同様に、 - i=1 i=1 のとき:k=2,3,4 k=2,3,4 の順に操作を行うと B=(1,4,3,2,5) B=(1,4,3,2,5) になるので、S1=1 S_1=1 - i=3 i=3 のとき:k=1,2,4 k=1,2,4 の順に操作を行うと B=(2,1,3,4,5) B=(2,1,3,4,5) になるので、S3=2 S_3=2 - i=4 i=4 のとき:k=1,2,3 k=1,2,3 の順に操作を行うと B=(2,3,4,1,5) B=(2,3,4,1,5) になるので、S4=4 S_4=4 です。