Por Samyra Almeida
Para resolver esse problema é necessário conhecimento sobre a técnica de sweep line e a estrutura da BIT (ou Binary Indexed Tree).
Segundo o enunciado temos que, dados dois pontos $$A$$ e $$B$$ e sendo $$A_x < B_x$$, temos que $$B$$ não domina $$A$$ se $$A_y > B_y$$.
Agora vamos utilizar a ideia do sweep line, primeiro iremos ordenar todos os pontos pela coordenada $$X$$. Com isso, note que dado qualquer conjunto válido $$C = {A, B, …, N}$$, sabemos que $$A_x < B_x < … < N_x$$ e $$A_y > B_y > … > N_y$$. Calculando a quantidade de conjuntos válidos até um determinado ponto $$i$$ temos que $$quantidade[i] =$$ $$\sum_{j = 1}^{i – 1} quantidade[j],$$ $$\forall$$ $$j_y > i_y$$.
Para calcularmos a quantidade de conjuntos válidos para o ponto $$i$$ de forma eficiente iremos utilizar uma estrutura de dados chamada BIT (ou Binary Indexed Tree) na coordenada $$Y$$ em que cada índice $$y$$ da BIT guarda a quantidade de conjuntos válidos no qual $$y$$ faz parte. De inicio a BIT estará vazia, mas iremos adicionando os conjuntos conforme o nosso algoritmo estiver rodando. Para descobrirmos quantos conjuntos válidos $$i$$ participa basta consultarmos a soma de $$i_y + 1$$ até $$m$$, onde $$m$$ é igual a maior coordenada $$Y$$ dentre todos os pontos presentes em $$S$$, fazendo $$quantidade[i] = sum(i_y + 1) + 1$$. Após isso, iremos atualizar a $$BIT[i]$$ fazendo $$add(i_y,$$ $$quantidade[i])$$. Enfim ao rodarmos esse algoritmo para todos os $$N$$ pontos temos que a resposta final será igual ao $$\sum_{k = 1}^{N} quantidade[k]$$.
Segue o código para maior entendimento:
https://gist.github.com/samyravitoria/fe81b84beb670f8a03180fc50c1c9a07
Deixe um comentário