E - I Hate Sigma Problems

Contest Duration: 2024-09-14(Sat) 12:00 - 2024-09-14(Sat) 13:40 (local time) (100 minutes) Back to Home

E - I Hate Sigma Problems Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $475$ 点

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。また、 $f(l,r)$ を以下で定義します。

$(A_l,A_{l+1},\ldots,A_{r-1},A_{r})$ に含まれる値の種類数

次の式の値を求めてください。

$\displaystyle \sum_{i=1}^{N}\sum_{j=i}^N f(i,j)$

制約

$1\leq N\leq 2\times 10^5$
$1\leq A_i\leq N$
入力される数値は全て整数

入力

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

 $N$ 
 $A_1$   $\ldots$   $A_N$

出力

答えを出力せよ。

入力例 1Copy

Copy

3
1 2 2

出力例 1Copy

Copy

$f(1,2)$ について考えます。 $(A_1,A_2)=(1,2)$ に含まれる値の種類数は $2$ なので $f(1,2)=2$ です。

$f(2,3)$ について考えます。 $(A_2,A_3)=(2,2)$ に含まれる値の種類数は $1$ なので $f(2,3)=1$ です。

$f$ の総和は $8$ となります。

入力例 2Copy

Copy

9
5 4 2 2 3 2 4 4 1

出力例 2Copy

Copy

Score : $475$ points

Problem Statement

You are given a sequence of integers $A = (A_1, A_2, \ldots, A_N)$ of length $N$ . Define $f(l, r)$ as:

the number of distinct values in the subsequence $(A_l, A_{l+1}, \ldots, A_r)$ .

Evaluate the following expression:

$\displaystyle \sum_{i=1}^{N}\sum_{j=i}^N f(i,j)$ .

Constraints

$1\leq N\leq 2\times 10^5$
$1\leq A_i\leq N$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $\ldots$   $A_N$

Output

Print the answer.

Sample Input 1Copy

Copy

3
1 2 2

Sample Output 1Copy

Copy

Consider $f(1,2)$ . The subsequence $(A_1, A_2) = (1,2)$ contains $2$ distinct values, so $f(1,2)=2$ .

Consider $f(2,3)$ . The subsequence $(A_2, A_3) = (2,2)$ contains $1$ distinct value, so $f(2,3)=1$ .

The sum of $f$ is $8$ .

Sample Input 2Copy

Copy

9
5 4 2 2 3 2 4 4 1

Sample Output 2Copy

Copy