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:
| #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