Solução de Lúcio Cardoso
Imagine que, para um índice fixo $$i$$ do vetor, sabemos o primeiro índice $$j \geq i$$ tal que o subvetor $$[i..j]$$ possui exatamente $$K$$ valores distintos. Então, por consequência, para todo índice $$l \geq j$$, o subvetor $$[i..l]$$ possuirá pelo menos $$K$$ valores distintos. Logo, há exatamente $$N-j+1$$ subvetores que satisfazem a condição do enuncidado e que começam em $$i$$. Assim, para resolver o problema, basta calcular tal índice $$j$$ para cada índice $$i$$ do vetor e somar $$N-j+1$$ na resposta a cada vez.
Para isso, vamos criar dois “ponteiros” (que na verdade apenas representam posições no vetor), $$l$$ e $$r$$. Imagine que para o $$l$$ atual queremos encontrar o primeiro valor de $$r \geq l$$ tal que $$[l..r]$$ possui $$K$$ elementos distintos. Se $$[l..r]$$ possuir menos que $$K$$ elementos distintos, aumentamos o valor de $$r$$ em 1; fazemos isso até que $$r$$ seja o índice desejado. Assim, como dito acima, haverão $$N-r+1$$ subvetores que começam em $$l$$ e que satisfaçam a condição do problema. Depois disso, repetimos o processo para os próximos valores de $$l$$. A observação importante é que não precisamos diminuir o índice $$r$$ em nenhum momento, já que para índices $$l$$ maiores, a posição $$r$$ desejada só irá aumentar.
Como os índices $$l$$ e $$r$$ só irão aumentar, $$l$$ percorrerá cada posição do vetor exatamente uma vez, assim como $$r$$. Então, a complexidade final será $$O(2n)$$ = $$O(n)$$. Para mais detalhes da implementação, confira o código abaixo:
| // 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"; | |
| } |

Comente