¿Cuántos Elementos Distintos?

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 256M

Authors:

leocar, humbertoyusta

Problem type

Allowed languages

C++

Dado un arreglo $a$ ~a~ de $n$ ~n~ elementos:

Sea $f(l, r)$ ~f(l, r)~ la cantidad de elementos distintos de $a_l, a_{l+1}, \cdots, a_r$ ~a_l, a_{l+1}, \cdots, a_r~.

Calcule $\sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} f(l,r)$

Es decir, la suma de $f(l, r)$ ~f(l, r)~ para todo par $(l, r)$ ~(l, r)~ tal que $1 \leq l \leq r \leq n$ ~1 \leq l \leq r \leq n~.

Entrada:

La primera línea contendrá un entero $n$ ~n~ $(1 \leq n \leq 200\,000)$ ~(1 \leq n \leq 200\,000)~, la cantidad de elementos de arreglo $a$ ~a~.

La segunda línea contendrá $n$ ~n~ elementos $a_1, a_2, \cdots a_n$ ~a_1, a_2, \cdots a_n~ $(1 \leq a_i \leq n)$ ~(1 \leq a_i \leq n)~, los elementos del arreglo $a$ ~a~.

Salida:

En la primera línea, imprima $\sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} f(l,r)$

Subtareas:

Subtarea 1: $n \leq 100$ ~n \leq 100~, todos los elementos de $a$ ~a~ son $1$ ~1~, es decir, $a_i = 1$ ~a_i = 1~ para $1 \leq i \leq n$ ~1 \leq i \leq n~ (10 puntos)
Subtarea 2: $n \leq 100$ ~n \leq 100~, todos los elementos de $a$ ~a~ son $1$ ~1~ o $2$ ~2~, es decir, $a_i \in \{1, 2\}$ ~a_i \in \{1, 2\}~ para $1 \leq i \leq n$ ~1 \leq i \leq n~ (17 puntos)
Subtarea 3: $n \leq 100$ ~n \leq 100~ (18 puntos)
Subtarea 4: $n \leq 5\,000$ ~n \leq 5\,000~ (15 puntos)
Subtarea 5: Sin restricciones adicionales (40 puntos)

Ejemplo de entrada

4
1 2 3 3

Ejemplo de salida

Comments

4

Kojima_Cubano_veriffedXD commented on Dec. 31, 2023, 5:54 a.m.

Muy buen problema 👏👏👏.