問題一覧 > 通常問題

No.3466 Mex Ranges

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 4
作問者 : dyktr_06 / テスター : tyawanmusi sepa38 hikikomori
ProblemId : 12941 / MMA Contest 021 (順位表) / 自分の提出
問題文最終更新日: 2025-12-18 04:06:06
MMA Contest 021の他の問題:

問題文

長さが $N$ の非負整数列 $A$ が与えられます。

$k = 0, 1, 2, \cdots, N$ について、以下の問題を解いてください。

  • $1 \leq l \leq r \leq N$ を満たす整数 $(l, r)$ の組であって、$\text{mex}(A_l, A_{l + 1}, \cdots, A_r) = k$ となるものの個数を求めよ。
ここで、$\text{mex}(x_1, x_2, \cdots, x_{p})$ は、$x_1, x_2, \cdots, x_{p}$ に含まれない最小の非負整数と定義します。

制約

  • $1 \leq N \leq 2 \times 10^{5}$
  • $0 \leq A_{i} \leq 10^{9}$
  • 入力はすべて整数

入力

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

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

$N + 1$ 行出力せよ。

$i$ 行目には、$k = i - 1$ のときの答えを出力せよ。

サンプル

サンプル1
入力
5
0 3 8 1 2
出力
10
3
1
0
1
0

例えば、$k = 1$ については、$(1, 1), (1, 2), (1, 3)$ が条件を満たします。

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