問題一覧 > 通常問題

No.2690 A present from B (Hard)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : 👑 eoeoeoeo / テスター : nu50218nu50218 ngtkanangtkana
1 ProblemId : 10760 / 自分の提出
問題文最終更新日: 2024-03-17 23:20:23

注意

こちらの問題の制約強化版です。

テスターのngtkanaさんによって考案されました。

問題文

来月に Alice さんと Bob さんを含む NN 人でプレゼント交換会を行うことになりました。 プレゼント交換会は Alice さんの家で行います。

Alice さんの家には NN 個の椅子が横一列に並んでおり、順に 1,2,,N1, 2, \dots, N の番号が付けられています。

プレゼント交換会では Alice さんが 11 番の椅子に座り、その他の N1N - 1 人の参加者は 22 番から NN 番 までの椅子から自由にひとつずつ選んで座ります。

このとき、NN 人全員がそれぞれ持参したプレゼントを持って座ります。

また、全員で事前に長さ MM の数列 A=(A1,A2,,AM)A = (A_1, A_2, \dots, A_M) を決めました。

プレゼント交換会はこの数列 AA を用いて以下のように行います。

  • 数列 AA の長さを A|A| とおく。各 i=1,2,,Ai = 1, 2, \dots, |A| に対して昇順に、次の操作を繰り返す。
    • AiA_i 番の椅子に座っている人と Ai+1A_i + 1 番の椅子に座っている人とが持っているプレゼントを交換する。

以上の操作を終えた後に、各自が持っているプレゼントを獲得できます。

Alice さんは Bob さんのプレゼントをどうしても獲得したいと思い、数列 AA を書き換える不正をすることにしました。

Alice さんは次の書き換え操作を好きなだけ行うことができます。

  • 現在の数列 AA の長さを A|A| とおく。整数 i (1iA+1)i \ (1 \leq i \leq |A| + 1) と整数 X (1XN1)X \ (1 \leq X \leq N - 1) を選び、 AA の先頭から ii 番目に XX を挿入する。

すなわち、 AA の任意の位置(先頭と末尾を含む)へ 11 以上 N1N-1 以下の任意の整数を挿入することが可能です。

当日 Alice さんは 11 番の椅子に座って皆を待ちます。 各 i=2,3,,Ni = 2, 3, \dots, N に対して、以下の値を求めてください。

  • プレゼント交換会で Bob さんが ii 番の椅子に座ったとき、Alice さんが Bob さんのプレゼントを 最終的に 獲得するために必要な書き換え操作の最小回数。

入力

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

NN MM
A1A_1 A2A_2 \dots AMA_M

出力

2iN2 \leq i \leq N に対して、Bob さんが ii 番の椅子に座ったときに Alice さんが Bob さんのプレゼントを獲得するために必要な書き換え操作の最小回数を BiB_i とします。

B2,B3,,BNB_2, B_3, \dots, B_N をこの順に空白区切りで標準出力へ一行で出力し、最後に改行してください。

制約

  • 入力はすべて整数
  • 2N1052 \leq N \leq 10^5
  • 1M1051 \leq M \leq 10^5
  • 1AiN1 (1iM)1 \leq A_i \leq N - 1 \ (1 \leq i \leq M)

サンプル

サンプル1
入力
3 2
1 2
出力
0 1

はじめ A=(1,2)A = (1, 2) です。

Bob さんが 22 番の椅子に座るとすると、AA に一つも値を挿入せずとも、11 番の椅子に座る Alice さんは Bob さんのプレゼントを獲得できます。

Bob さんが 33 番の椅子に座るとすると、たとえば AA の先頭から 11 番目に 22 を挿入して A=(2,1,2)A = (2, 1, 2) とすることで Alice さんは Bob さんのプレゼントを獲得できます。

サンプル2
入力
4 3
1 2 3
出力
0 1 2

椅子は横一列に並んでいます。 11 番の椅子に座っている人と 44 番の椅子に座っている人の間ではプレゼントを交換できない点に注意してください。

サンプル3
入力
4 3
1 3 2
出力
0 1 1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。