Editorial for ¿Cuántos Elementos Distintos?

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: aniervs, humbertoyusta

Subtarea 1

$a_i = 1$ ~a_i = 1~

Entonces, $f(l, r) = 1$ ~f(l, r) = 1~ por lo que la respuesta es $1 + 2 + \cdots + n$ ~1 + 2 + \cdots + n~ , o $\frac{n(n+1)}{2}$ ~\frac{n(n+1)}{2}~

Subtarea 2

$a_i \in \{1, 2\}; n \le 100$ ~a_i \in \{1, 2\}; n \le 100~

La solución de la subtarea 3 sirve para esta subtarea, aquí es un poco más facil porque todos los elementos son $1$ ~1~ o $2$ ~2~.

Subtarea 3

$n \le 100$ ~n \le 100~.

Es suficiente iterar por todos los rangos $[l, r]$ ~[l, r]~ y computar por cada uno, la cantidad de elementos distintos en tiempo lineal. Para hacerlo, llevamos un arreglo de marcados, tal que mark[x] = true significa que $x$ ~x~ aparece en el rango analizado. Luego, la respuesta es la cantidad valores true en mark[].

Complejidad: $\mathcal{O}(n^3)$ ~\mathcal{O}(n^3)~.

Subtarea 4

De la subtarea anterior, estamos computando varias cosas múltiples veces. Observemos que entre el rango $[l,r]$ ~[l,r]~ y el rango $[l,r+1]$ ~[l,r+1]~ no hay mucha diferencia en la información que se lleva. En lugar de reiniciar mark[] cada vez e iterar por $[l, r+1]$ ~[l, r+1]~ modificando mark[], podemos simplemente fijar $l$ ~l~, luego iterar por $r$ ~r~ en orden creciente, y actualizando solo $mark[a_r]$ ~mark[a_r]~ en cada momento. Cada vez que mark[x] cambia de false a true, le añadimos 1 a la respuesta.

Complejidad: $\mathcal{O}(n^2)$ ~\mathcal{O}(n^2)~

Subtarea 5

Digamos que $nxt(i)$ ~nxt(i)~ es el primer $j > i: a_j = a_i$ ~j > i: a_j = a_i~, y si no existe tal $j$ ~j~, digamos que es $n + 1$ ~n + 1~.

Podemos considerar $f(l, r)$ ~f(l, r)~ como la cantidad de $i \in [l, r]: nxt(i) > r$ ~i \in [l, r]: nxt(i) > r~.

Entonces, la "contribución" de cada $i$ ~i~ a la respuesta es la cantidad de rangos $[l, r]: i \in [l,r]$ ~[l, r]: i \in [l,r]~ y $nxt(i) > r$ ~nxt(i) > r~.

Tenemos que $1 \le l \le i$ ~1 \le l \le i~, y que $i \le r < nxt(i)$ ~i \le r < nxt(i)~. Por tanto, la contribución de $i$ ~i~ a la respuesta es $(nxt(i) - i) \cdot i$ ~(nxt(i) - i) \cdot i~.

La solución entonces se puede expresar como $\displaystyle\sum_{i = 1}^n (nxt(i) - i)\cdot i$ . Esto toma tiempo lineal.

El cuello de botella de la solución está en computar $nxt(i)$ ~nxt(i)~. Podemos hacerlo en tiempo cuadrático simplemente iterando por $j > i$ ~j > i~ hasta que encontremos un $j : a_j = a_i$ ~j : a_j = a_i~, lo cual es suficiente para aceptar esta subtarea.

Para subtarea, simplemente computamos $nxt()$ ~nxt()~ en tiempo lineal en total. Cómo, podemos ir de derecha a izquierda, actualizando la posición de cada valor.

Otra solución sería, sumar las longitudes de todos los intervalos, y luego para cada elemento $x$ ~x~, restar todos los intervalos en los cuales $x$ ~x~ no está presente, lo cual se puede hacer, siendo $v_1, v_2, \cdots, v_{cnt_x}$ ~v_1, v_2, \cdots, v_{cnt_x}~ las ocurrencias de $x$ ~x~ ( $v_0 = 0$ ~v_0 = 0~ y $v_{cnt_x+1} = n+1$ ~v_{cnt_x+1} = n+1~), como $\displaystyle\sum_{i = 1}^{cnt_x+1} \frac{(v_i - v_{i-1}) \cdot (v_i - v_{i-1} - 1)}{2}$ .

Comments

There are no comments at the moment.