Noic - Problema da Semana 49 - Nível Intermediário

noic-semana49-intermed.cpp

// Noic - Semana 49 - Intermediário
// Complexidade: O(n)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxv = 1e6+10;

typedef long long ll;

// freq guarda a frequência de cada número no intervalo [l..r] atual
int num[maxn], freq[maxv];

int main(void)
{
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++) cin >> num[i];

	int l = 1, r = 1, qtd = 1; // qtd é a quantidade de números distintos em [l..r]
	ll ans = 0ll; // resposta do problema

	freq[num[1]]++; // começamos na posição 1, então no momento, o 1o número aparece uma vez

	while (l <= n) // primeiro índice do subvetor
	{
		while (r <= n && qtd < k) // aumentamos r até que [l..r] tenha K elementos distintos
		{
			r++;
			freq[num[r]]++; // aumento a frequência do número na nova posição de r

			// se a freq do número atual é exatamente 1, ele é um elemento novo no subvetor
			// logo, a quantidade de elementos distintos aumenta
			if (freq[num[r]] == 1) qtd++;
		}

		// subvetores para a resposta que começam em l (último índice maior ou igual a r)
		ans += 1ll*(n-r+1);

		// o l agora vai virar l+1, então diminuímos a freq de num[l] em 1
		// logo se a freq dele em [l..r] for 1, em [l+1..r] será 0, ou seja, teremos
		// um elemento distinto a menos 
		if (freq[num[l]] == 1) qtd--;
		freq[num[l]]--;

		l++;
	}

	cout << ans << "\n";
}