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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 1e5+10, mod = 1e9+7; | |
| int n, m, bit[maxn], quantidade[maxn]; | |
| struct point{ | |
| int x, y; | |
| bool operator<(const point& o) const{ | |
| if(x != o.x) return x < o.x; | |
| return y < o.y; | |
| } | |
| } p[maxn]; | |
| void add(int i, int v){ | |
| while(i) | |
| { | |
| bit[i] = (bit[i]%mod + v)%mod; | |
| i-=(i&-i); | |
| } | |
| } | |
| int sum(int i) | |
| { | |
| int soma = 0; | |
| for(; i <= m ; i += (i&-i)) | |
| { | |
| soma = (soma%mod +bit[i])%mod; | |
| } | |
| return soma; | |
| } | |
| int main() | |
| { | |
| cin >> n; | |
| for(int i = 1 ; i <= n ; ++i) | |
| { | |
| cin >> p[i].x >> p[i].y; | |
| m = max(m, p[i].y); | |
| } | |
| sort(p + 1, p + n + 1); | |
| int resp = 0; | |
| for(int i = 1 ; i <= n ; ++i) | |
| { | |
| quantidade[i] = (sum(p[i].y + 1)%mod + 1)%mod; | |
| add(p[i].y, quantidade[i]); | |
| resp = (resp%mod + quantidade[i])%mod; | |
| } | |
| cout << resp << "\n"; | |
| return 0; | |
| } |
Comente