Aula por Arthur Lobo
Nesta aula, abordaremos uma técnica eficiente para contar a quantidade de inversões em um array usando a estrutura de dados Binary Indexed Tree (BIT).
Conhecimento prévio necessário:
O que é uma inversão?
Dado um Array com $$N$$ elementos $$A_1,A_2,…,A_N$$, dizemos que $$i$$ e $$j$$ estão invertidos (são uma inversão) se $$i < j$$ e $$A_i > A_j$$, ou seja, eles estão fora de ordem um em relação ao outro. Formalmente, o par $$(i,j)$$ é uma inversão $$\iff$$ $$i < j$$ e $$A_i > A_j$$.
A quantidade de inversões é a quantidade de pares $$(i,j)$$ que são uma inversão. Por exemplo, no array $$A = [3,1,2]$$ existem duas inversões: $$(3, 1)$$ e $$(3, 2)$$.
Comprimindo o Array
Note que a o real valor em cada posição no array $$A$$ não importa, só importa a os valores de cada posição em relação aos outros valores presentes no array. Por exemplo, os arrays $$[3,10,6]$$ e $$[2,4,3]$$ são equivalentes em relação as inversões.
Por conta disso, vamos querer fazer com que os valores no array inicial sejam os menores possíveis, deixando todos eles no intervalo $$[1,N]$$. Os dois arrays citados a cima virariam $$[1,3,2]$$, em que todos os valores estão de $$1$$ até $$3$$ ($$N$$).
Para fazer isso, basta utilizarmos a técnica de compreensão de coordenadadas no array inicial. Veja aqui a aula do NOIC sobre compressão de coordenadas: Link da Aula.
Contando as inversões
Vamos contar, para cada $$i$$, quantos $$j$$ ($$i < j$$) existem tal que $$(i,j)$$ é uma inversão. Nosso objetivo será percorrer o array do final até o começo mantendo uma BIT em que a posição $$x$$ guarda quantos elementos iguais a $$x$$ já foram percorridos, então quando estivermos em $$i$$, basta contarmos quantos elementos $$< A_i$$ já foram percorridos fazendo uma query na BIT.
Desse jeito, quando estamos em $$i$$ vamos realizar os seguintes passos:
- Sabemos que já percorremos $$A_{i+1},A_{i+2},…,A_N$$ e eles já foram somados na BIT.
- Para contar quantos $$j$$ existem tal que $$(i,j)$$ é uma inversão, fazemos uma query na BIT contando quantos elementos menores que $$A_i$$ já foram somados na BIT e adicionamos isso na resposta: quantidade_de_inversões+= $$query\_BIT(A_i-1)$$.
- Agora adicionamos $$A_i$$ na BIT, somando $$+1$$ na posição $$A_i$$: $$update\_BIT(A_i,+1)$$.
- Agora podemos seguir para $$i-1$$, mas com os elementos $$A_{i},A_{i+1},…,A_N$$ adicionados na BIT.
Por exemplo, no array $$A = [3,1,2]$$, a query retornaria 0 nas posições $$2$$ e $$3$$, mas retornaria $$2$$ na posição $$1$$. Já no array $$A = [3,2,1]$$, a query retornaria $$0, 1$$ e $$2$$ nas posições $$3,2$$ e $$1$$, respectivamente.
Obs: Não esqueça de utilizar long long para contar as inversões!