問題一覧 > 通常問題

No.1526 Sum of Mex 2

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : Rheo TommyRheo Tommy / テスター : nok0nok0 penguinmanpenguinman yuto1115yuto1115
0 ProblemId : 6392 / 自分の提出
問題文最終更新日: 2021-07-10 15:05:06

問題文

長さ $N$ の数列 $A$ が与えられます。数列 $A$ の空でない連続部分列（これは $N(N+1)/2$ 個あります）全てに対して Mex を求め、その総和を出力してください。

より厳密には、以下のとおりです。

数列 $T$ に対して、関数 $f(T)$ を次のように定義します。

\[ f(T) = (x \in \mathbb{Z},x \geq 1, x \notin T)\ \text{を満たす最小の}\ x \]

このとき、以下の値を求めてください。

\[ \sum_{1 \leq l \leq r \leq N} f(\{A_l, A_{l+1} \dots A_r\}) \]

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
  • $1 \leq N \leq 10^5$
  • $ 1 \leq A_i \leq N\ (1 \leq i \leq N)$
  • 入力は全て整数

出力

答えを出力してください。

サンプル

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

それぞれの空でない連続部分列 $T$ に対する $f(T)$ の値は以下のようになります。

  • $T=\{1\}$, $f(T) = 2$
  • $T=\{2\}$, $f(T) = 1$
  • $T=\{3\}$, $f(T) = 1$
  • $T=\{1,2\}$, $f(T) = 3$
  • $T=\{2,3\}$, $f(T) = 1$
  • $T=\{1,2,3\}$, $f(T) = 4$

したがって、その総和は$12$ となります。

サンプル2
入力
6
1 2 3 1 2 3
出力
58

サンプル3
入力
30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
出力
930

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