No.1526 Sum of Mex 2

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1526 Sum of Mex 2

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 :

Rheo Tommy / テスター :

nok0

penguinman

yuto1115

0 ProblemId : 6392 / 自分の提出

問題文最終更新日: 2021-07-10 15:05:06

問題文

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

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

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

f (T) = (x \in Z, x \geq 1, x \notin T) を満たす最小の 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

出力

それぞれの空でない連続部分列 $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

出力

サンプル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

出力

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

yukicoder

No.1526 Sum of Mex 2

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力