It's Mooin' Time II

Explicación

Consideremos el arreglo $[4, 2, 3, 3, 6, 3, 3]$ . Con el primer par de treses, podemos formar los moos $[4, 3, 3]$ y $[2, 3, 3]$ . Luego, con el último par de treses, podemos formar $[6, 3, 3]$ . Sin embargo, observemos que con el último par también podemos formar $[4, 3, 3]$ y $[2, 3, 3]$ . De aquí surge la observación clave: podemos formar todos los moos posibles usando solo las dos últimas ocurrencias.

Así, para cada candidato como entero que se repite, la cantidad de moos que podemos formar es la cantidad de enteros distintos antes de la penúltima ocurrencia (si existe). Sin embargo, como el primer entero de un moo no es igual al segundo ni al tercero, hay que restar uno de nuestro conteo si hay una tercera ocurrencia del entero repetido candidato.

Para calcular de forma eficiente la cantidad de números distintos a la izquierda de cualquier índice, usamos un conjunto y precomputamos la cantidad de valores distintos de cada prefijo consultando la longitud del conjunto.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	// hallar los índices de las ocurrencias de cada número
	vector<vector<int>> frequency(n + 1);
	for (int i = 0; i < n; i++) { frequency[a[i]].push_back(i); }
 
	// precomputar la cantidad de valores distintos a la izquierda de cada índice
	vector<int> num_distinct(n);
	set<int> distinct_vals;
	for (int i = 0; i < n; i++) {
		num_distinct[i] = distinct_vals.size();
		distinct_vals.insert(a[i]);
	}
 
	// calcular la respuesta
	long long ans = 0;
	for (int num = 1; num <= n; num++) {
		if (frequency[num].size() >= 2) {
			int second_last_index = frequency[num][frequency[num].size() - 2];
			ans += num_distinct[second_last_index];
			if (frequency[num].size() >= 3) { ans--; }
		}
	}
 
	cout << ans << "\n";
}


n = int(input())
array = [int(x) for x in input().split()]
# hallar los índices de las ocurrencias de cada número
frequency = dict()
for i in range(n):
	if array[i] in frequency:
		frequency[array[i]].append(i)
	else:
		frequency[array[i]] = [i]
 
# precomputar la cantidad de valores distintos a la izquierda de cada índice
num_distinct = []
distinct_vals = set()
for i in range(n):
	num_distinct.append(len(distinct_vals))
	distinct_vals.add(array[i])
 
# calcular la respuesta
ans = 0
for num in frequency:
	if len(frequency[num]) >= 2:
		ans += num_distinct[frequency[num][-2]]
		if len(frequency[num]) >= 3:
			ans -= 1
print(ans)