問題一覧 > 通常問題

No.1526 Sum of Mex 2

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 22
作問者 : Rheo Tommy / テスター : nok0 penguinman yuto1115
お気に入りにしたユーザー ProblemId : 6392 / 自分の提出
問題文最終更新日: 2026-10-22 23:06:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given a sequence $A$ of length $N$. Find the Mex of every non-empty contiguous subarray of $A$ (there are $N(N+1)/2$ of them), and print the sum of these values.

More formally, the problem is as follows.

For a sequence $T$, define the function $f(T)$ as follows.

\[ f(T) = (x \in \mathbb{Z},x \geq 1, x \notin T)\ \text{: the smallest such}\ x \]

Find the following value.

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

Input

$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)$
  • All inputs are integers.

Test cases containing the string evil do not satisfy the constraints, but they do not affect AC. The constraints for test cases containing evil are
$1 \leq N \leq 3 \times 10^5$, $1 \leq A_i \leq N\ (1 \leq i \leq N)$.

Output

Print the answer.

Sample

Sample 1
Input
3
1 2 3
Output
12

The value of $f(T)$ for each non-empty contiguous subarray $T$ is as follows.

  • $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$

Therefore, their sum is $12$.

Sample 2
Input
6
1 2 3 1 2 3
Output
58

Sample 3
Input
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
Output
930

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