atcoder#ARC069C. [ARC069E] Frequency

[ARC069E] Frequency

题目描述

すぬけくんは数列を作るのが好きです。

1 1 から N N までの番号がついた石の山があります。 i i 番の石の山は ai a_i 個の石からなります。

すぬけくんは以下の手順により長さ Σai Σa_i の数列 s s を構成することにしました。

  1. 石の数が最大である山のうち、最も番号が小さい山の番号を x x として、s s の末尾に x x を追加する
  2. 石が 1 1 個以上存在する山を 1 1 つ選んで、選んだ山から石を 1 1 つ取り除く
  3. 石が 1 1 個以上存在する山が存在するなら 1. 1. へ、そうでなければ数列の構成を終了する

s s が辞書順で最小の数列となるようにしたとき、s s 1,2,3,...,N 1,2,3,...,N という数がそれぞれいくつ含まれるか求めなさい。

输入格式

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

N N a1 a_1 a2 a_2 ... ... aN a_{N}

输出格式

答えを N N 行に出力せよ。i i 行目では辞書順で最小の s s における i i の出現回数を出力せよ。

题目大意

给定 NN 堆石子,第 ii 堆大小为 AiA_i

现在你需要构造一个长度 Ai\sum A_i 的序列 SS,构造流程如下:

  • 找到当前石子数量最多的那堆石子,如果有多个则取最前面哪个,将下标记作 PP,将 PP 写在 SS 末尾。

  • 选择一堆石子,拿一个石子出来。

  • 如果还有石子剩余,重复这个流程。

现在需要你最小化 SS 的字典序,输出 1n1 \sim nSS 中出现了多少次。

2
1 2
2
1
10
1 2 1 3 2 4 2 5 8 1
10
7
0
4
0
3
0
2
3
0

提示

制約

  • 1  N  105 1\ ≦\ N\ ≦\ 10^{5}
  • 1  ai  109 1\ ≦\ a_i\ ≦\ 10^{9}

Sample Explanation 1

以下の手順で辞書順最小であるような数列が構成できます。 - 石の数が最大であるような山は 2 2 番なので 2 2 s s に追加する。その後、番号 2 2 の山から石を 1 1 つ取り除く。 - 石の数が最大であるような山は 1 1 番と 2 2 番なので、最も番号が小さい 1 1 s s に追加する。その後、番号 2 2 の山から石を 1 1 つ取り除く。 - 石の数が最大であるような山は 1 1 番なので 1 1 s s に追加する。その後、番号 1 1 の山から石を 1 1 つ取り除く。 このときできる数列は (2,1,1) (2,1,1) となります。1 1 2 2 つ含まれ、2 2 1 1 つ含まれます。