atcoder#ABC279E. [ABC279E] Cheating Amidakuji

[ABC279E] Cheating Amidakuji

配点 : 500500

問題文

11 以上 N1N-1 以下の整数からなる長さ MM の数列 A=(A1,A2,,AM)A=(A_1,A_2,\dots,A_M) が与えられます。 i=1,2,,Mi=1,2,\dots,M について、以下の質問に答えてください。

  • 数列 B=(B1,B2,,BN)B=(B_1,B_2,\dots,B_N) がある。最初、各 jj について Bj=jB_j=j である。今から、k=1,2,,i1,i+1,,Mk=1,2,\dots,i-1,i+1,\dots,M の順に以下の操作を行う (すなわち、ii を除いた 11 以上 MM 以下の整数 kk について、昇順に以下の操作を行う)。- BAkB_{A_k}BAk+1B_{A_k+1} の値を入れ替える。
  • BAkB_{A_k}BAk+1B_{A_k+1} の値を入れ替える。
  • 全ての操作が終了した段階で、Bj=1B_j=1 を満たす jj の値を SiS_i と定義する。SiS_i を求めよ。

制約

  • 2N2×1052 \leq N \leq 2\times 10^5
  • 1M2×1051 \leq M \leq 2\times 10^5
  • 1AiN1 (1iM)1 \leq A_i \leq N-1\ (1\leq i \leq M)
  • 入力は全て整数

入力

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

NN MM

A1A_1 A2A_2 \dots AMA_M

出力

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

5 4
1 2 3 2
1
3
2
4

i=2i = 2 のとき、操作によって BB は以下のように変化します。

  • 最初、B=(1,2,3,4,5)B = (1,2,3,4,5)
  • k=1k=1 として操作を行う。すなわち B1B_1B2B_2 の値を入れ替えて、B=(2,1,3,4,5)B = (2,1,3,4,5)
  • k=3k=3 として操作を行う。すなわち B3B_3B4B_4 の値を入れ替えて、B=(2,1,4,3,5)B = (2,1,4,3,5)
  • k=4k=4 として操作を行う。すなわち B2B_2B3B_3 の値を入れ替えて、B=(2,4,1,3,5)B = (2,4,1,3,5)

全ての操作が終了した段階で B3=1B_3=1 であるため、S2=3S_2 = 3 です。

同様に、

  • i=1i=1 のとき:k=2,3,4k=2,3,4 の順に操作を行うと B=(1,4,3,2,5)B=(1,4,3,2,5) になるので、S1=1S_1=1
  • i=3i=3 のとき:k=1,2,4k=1,2,4 の順に操作を行うと B=(2,1,3,4,5)B=(2,1,3,4,5) になるので、S3=2S_3=2
  • i=4i=4 のとき:k=1,2,3k=1,2,3 の順に操作を行うと B=(2,3,4,1,5)B=(2,3,4,1,5) になるので、S4=4S_4=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