Aula por Caique Paiva
Conhecimento prévio necessário:
O intuito dessa aula é resolver o seguinte problema:
Dado uma sequência $$a_1, a_2, \cdots , a_n$$, ache o tamanho da maior subsequência crescente de $$a$$.
Por exemplo, na sequência $$ \{ 1, 3, 7 ,2, 5, 4, 10 \} $$, a maior subsequência crescente é $$ \{ 1, 3, 5, 10 \} $$, logo a resposta é $$4$$. Vamos fazer $$N \le 2 \cdot 10^5$$ e $$a_i \le 10^9$$ para todo $$i$$.
Vamos achar um algoritmo que roda em $$O(n \log )$$ com uma dp, e a melhor parte desse algoritmo é que podemos aplicar a mesma ideia para outros problemas.
A dp será a seguinte: Defina como $$dp(x)$$ para ser a maior subsequênca crescente no qual último valor dessa subsequência é $$x$$. A ideia do problema é começar a calcular essa dp no intervalo $$[1, 1]$$, e depois passar para o intervalo $$[1, 2]$$, depois para o intervalo $$[1, 3]$$, e ir até o intervalo $$[1, n]$$.
Com isso, suponha que calculamos essa dp para o intervalo $$[1, i]$$, então, vamos calcular ela para o intervalo $$[1, i+1]$$. Primeiro, veja que o único valor da dp que nós vamos mudar é o de $$dp[a_{i+1}]$$, pois as outras subsequências (Ou seja, as que não terminam em $$a_{i+1}$$) estão inclusas em $$[1, i]$$. Com isso, vamos atualizar $$dp[a_{i+1}]$$.
Com isso, para toda subsequência crescente que acaba em um número $$x \le a_{i+1}$$, então, se incluirmos o $$a_{i+1}$$ nela, conseguimos uma subsequência crescente que acaba em $$a_{i+1}$$, e ela vai ter tamanho máximo de $$dp(x)+1$$! Além disso, se $$x \ge a_{i+1}$$, não podemos incluir $$a_{i+1}$$ na subsequência, ou seja, não contamos esse caso na dp. Portanto, a fórmula para calcular essa transição vai ser
$$dp(a_{i+1}) = max_{1 \le x \le a_{i+1}} (dp(x)) + 1$$
Porém, temos dois problemas nessa solução, mas eles são tranquilos de resolver:
- Primeiro é o fato de que $$a_i \le 10^9$$. Isso é um problema, pois precisamos criar um vetor para $$dp$$ de tamanho $$max (a_i)$$, que pode ser igual a $$10^9$$, resultando num MLE. Para resolver isso, basta fazer uma compressão de coordenadas, fazendo $$a_i \le N$$.
- O segundo problema é que, para calcular $$max_{1 \le x \le a_{i+1}} dp(x)$$, fazemos um algoritmo em $$O(a_{i+1})$$, ou seja, calcular essa dp é em $$O(N^2)$$ . Para resolver isso, basta ver que, se fizermos uma segtree de máximo, e então, em cada passo, calculamos a query de $$[1, a_{i+1}]$$, e fazemos o update de $$a_{i+1}$$ como descrito acima, e então, a transição fica $$O(log n)$$.
Com isso, achamos o algoritmo em $$O(Nlog)$$.