Solução escrita por Márcio Vitor
Conhecimentos prévios:
Subtarefa 2 ($p_i = i$ para todo $1 \le i \le N$) (7 pontos):
Nessa subtarefa a árvore formada é como se fosse uma linha inclinada para direita, todo $i$ adicionado é comparado com todos os $i-1$ elementos anteriores até terminar no ponto mais à direita.
Ou seja a quantidade de comparações é $0 + 1 + 2 + 3 + \cdots + N-1 = \frac{N \cdot (N-1)}{2}$.
Complexidade: $O(1)$
Subtarefa 3 (A permutação é tal que primeiro aparecem todos os números
ímpares em ordem crescente, e depois todos os pares em ordem crescente) (9 pontos):
Seja $ci,cp$ a contagem de ímpares e pares na permutação respectivamente, Similar a subtarefa 2 os ímpares vão fazer $\frac{ci \cdot (ci-1)}{2}$, e os pares vão seguir um padrão similar: o $2$ se compara com o $1,3$, o $4$ se comparar com o $1,3,5$, …, assim os pares fazem: $2 + 3 + \cdots + cp+1 = \frac{cp \cdot (cp+3)}{2} comparações$.
Portanto basta imprimir: $\frac{cp \cdot (cp+3)}{2} + \frac{ci \cdot (ci-1)}{2}$ se N for ímpar e $\frac{cp \cdot (cp+3)}{2} + \frac{ci \cdot (ci-1)}{2} – 1$ se N for par.
Note que $ci = \lceil N/2 \rceil$ e $cp = \lfloor N/2 \rfloor$ em uma permutação de tamanho $N$, assim é possível codar em $\mathcal{O}(1)$ ao invés de contar iterando pelo vetor.
Subtarefa 4 ($N \le 1000$) (17 pontos):
Para essa subtarefa para cada elemento $i$ do vetor vamos iterar $j$ de $1$ à $i-1$ para descobrir quais desses o nosso $p_i$ terá que ser comparado, vamos manter duas variáveis $L, R$ (o valor do último cara que viramos a direita e esquerda respectivamente). $p[i]$ está à direita de $L$ e à esquerda de $R$.
Ou seja, se o $p_j \lt L$ ou $p_j \gt R$ ele estará em outra subárvore (à esquerda de $L$ ou à direita de $R$), então podemos ignora-lo.
Caso contrario: Verifique se $p_i$ terá de ir a direita ou a esquerda de $p_j$ e atualize $L,R$ de acordo.
Para mais detalhes veja o código abaixo, complexidade: $\mathcal{O}(N^2)$.
Subtarefa 5 (É garantido que o número de comparações feitas ao inserir
qualquer número é no máximo 100) (12 pontos):
Guarde e calcule a árvore conforme adicionamos os elementos, para cada um descendo até achar a posições correta e adicionando ele lá. Como ele garante que não vamos fazer muitas comparações a complexidade fica: $\mathcal{O}(N \cdot H)$ ($H$ = máximo de comparações por elemento.
Subtarefa 6 ($−10 \le p_i − i \le 10$ para todo $1 \le i \le N$) (24 pontos):
para um $i$ qualquer sabemos que todo $j \le i-20 \implies p_j \le j+10 \implies p_j \le i-10$ sabemos que $p_i \ge i-10$ então $p_j \le p_i$.
Ou seja para todos os valores de $1$ a $i-20$ vamos sempre ir a direita, ou seja temos que descobrir quantas comparações a direita para chegar no $i-20$ isso pode ser feito contando quantos máximos de prefixos terão até certo indice, e depois rodamos o mesmo algoritmo da subtarefa 4 nos próximos 19 caras.
Complexidade: $\mathcal{O}(N \cdot max(p_i -i))$
Subtarefa 7 (Sem restrições adicionais) (100 pontos):
A principal observação para resolver esse problema é que todo filho de uma folha da árvore representa um intervalo de elementos contínuos, que caso algum elemento esteja dentro do intervalo ele descerá ate essa folha para se tornar este filho.
Por exemplo imagine que os primeiros 4 elementos de uma permutação de tamanho 12 sejam [5,2,7,8]:
- Um valor entre $1$ e $1$ irá pra esquerda do $2$.
- Um valor entre $3$ e $4$ irá pra direita do $2$.
- Um valor entre $6$ e $6$ irá para esquerda do $7$.
- nenhum valor pode ir para esquerda do $8$(pois não existe inteiro entre 7 e 8).
- Um valor entre $9$ e $12$ irá para direita do 8.
Vamos manter esses intervalos em um $\texttt{set}$ junto com a quantidade de comparações para chegar nele, para descobrir qual intervalo o $p_i$ está contido basta descobrir qual o primeiro a direita dele usando $\texttt{lower_bound}$ do set no par ${p_i+1,0}$ e então pegando o anterior.
Depois adicione a resposta a quantidade de comparações desse intervalo, seja ele $[L,R]$ e divida ele em dois $[L,p_i-1]$ e $[p_i+1,R]$ ambos terão uma comparação a mais.
Inicialmente o $\texttt{set}$ conterá apenas $[1,N]$, complexidade final: $\mathcal{O}(N \cdot log_2 (N))$.
Nota: Se lembre de remover intervalos vazios que nenhum elemento pode pertencer a ele.