Escrito por Caique Paiva
Conhecimentos Prévios Necessários
Suponha que a nossa sequência de bombons $$[a_1, a_2, \cdots, a_n]$$ tem uma divisão boa $$(l_1, r_1), (l_2, r_2), \cdots, (l_k, r_k)$$, com $$k > 2$$, então, veja que $$(l_1, r_2), (l_3, r_3), \cdots, (l_k, r_k)$$ também é uma solução válida, pois, como o MEX de $$(l_1, r_1)$$ é igual o de $$(l_2, r_2)$$, então $$(l_1, r_2)$$, também terá o mesmo MEX, pois esse intervalo vai conter todos os números de $$0$$ até $$MEX-1$$ e não vai conter $$MEX$$. Portanto, provamos que, caso tenhamos uma divisão boa de tamanho $$k$$, também temos uma divisão boa de tamanho $$k-1$$. Em particular, fazendo essa operação de juntar várias vezes, conseguimos chegar em somente $$2$$ intervalos.
Agora, só precisamos ir atrás de $$2$$ intervalos $$(1, i), (i+1, n)$$ tal que o MEX deles dois sejam o mesmo. Então, chame de $$pref[N]$$ um vetor de $$N$$ elementos, onde $$pref[i] = MEX$$ de $$a_1$$ até $$a_i$$. Vamos ver como calcular ele.
Primeiro, seja $$mark[N]$$ um vetor que vai guardar quais elementos estão na nossa sequência (Ou seja, $$mark[i] = 1$$ caso $$i$$ esteja na sequência, e $$0$$ caso contrário). Inicialize $$pref[0] = 0$$ e $$mark[i] = 0$$ para todo i. Então, façamos um for com $$i = 1$$ indo até $$n$$, e no passo $$i$$, vamos calcular $$pref[i]$$:
- Primeiro, veja que $$pref[i-1] = MEX$$ de $$a_1$$ até $$a_{i-1}$$, então, para calcularmos $$pref[i]$$, basta adicionarmos $$a_i$$ ao $$MEX$$ de i-1. Então, faça $$mark[a[i]] = 1$$, e veja os seguintes casos:
- Se $$mark[pref[i-1]] = 0$$, significa que $$pref[i-1]$$ não foi adicionado ao vetor, então o mex de $$a_1$$ até $$a_i$$ continua sendo $$pref[i-1]$$, logo, $$pref[i] = pref[i-1]$$
- Caso contrário, então todos os elementos de $$0$$ até $$pref[i-1]$$ estão em $$a_1$$ até $$a_i$$, faça $$pref[i] = pref[i-1]$$, e faça o seguinte while:
- while(v[pref[i]] > 0) pref[i]++;
- Ou seja, enquanto $$pref[i]$$ pertencer a $$a_1$$ até $$a_i$$, aumente $$pref[i]$$. Isso vai achar qual é o mex de $$a_1$$ até $$a_i$$.
Portanto, conseguimos calcular $$pref[i]$$ para todo $$i$$ em $$O(N)$$! Para finalizar, chame de $$suf[N]$$ um vetor de $$N$$ elementos onde $$suf[i] = MEX$$ de $$a_i$$ até $$a_n$$ (Ele vai ser calculado quase da mesma maneira que pref). Então basta procurar algum $$i$$ tal que $$pref[i] = suf[i+1]$$. Caso ele exista, imprima os inervalos $$[1, i]$$ e $$[i+1, n]$$ como resposta. Caso não exista, imprima -1. Complexidade final: $$O(N)$$.