Por Samyra Almeida
Para resolver esse problema é necessário conhecer sobre a estrutura de dados BIT (Binary Indexed Tree ou Árvore de Indexação Binária, em tradução livre) também conhecida como Árvore de Fenwink (Fenwick Tree) e sobre o Algoritmo de Mo (esse tutorial está em inglês).
Bem, essa questão é bem semelhante ao Algoritmo de Mo tradicional (quantas vezes um determinado número aparece em um intervalo de $$l$$ até $$r$$), só que como queremos saber quantos prédios são maiores a uma determinada altura $$y$$, utilizaremos uma BIT de frequência, onde a função $$upd(p,$$ $$val)$$ atualizará o intervalo $$1$$ até $$p$$ e a $$query(p)$$ consultará quantos prédios existem com a altura de $$p$$ até $$maxv$$ (maior altura possível que segundo o enunciado da questão é $$10⁶$$). Sendo assim ao adicionarmos um prédio $$t$$ ao intervalo iremos fazer $$upd(v[t],$$ $$1)$$ e ao removermos um prédio $$t$$ faremos $$upd(v[t],$$ $$-1)$$, vale lembrar que no vetor $$v[]$$ temos a altura de todos os prédios. E para consultar quantos prédios existem com altura maior que $$y$$ iremos fazer $$query(y+1)$$, a cada pergunta de Sufia iremos salvar a resposta do intervalo no vetor $$ans[]$$. Ao final no algoritmo basta imprimirmos o vetor $$ans[]$$.
Para maior compreensão, segue o código solução:
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 3e6+10, root = 320, maxv = 1e6; | |
| int resp, n, q, v[maxn], f[maxn], ans[maxn], bit[maxn]; | |
| struct Q | |
| { | |
| int l, r, y, id, b; | |
| bool operator<(const Q& o) const | |
| { | |
| if(b == o.b) // otmização de paridade, não precisa (NESSE CASO) mas não custa nada sempre colocar =) | |
| { | |
| if(b&1) return r > o.r; // se o bloco for ímpar, ordenamos do maior r para o menor | |
| else return r < o.r; // se for par, ordenamos do menor r para o maior | |
| } | |
| return b < o.b; // se estivermos em blocos diferente ordenamos do menor para o maior bloco | |
| } | |
| } qr[maxn]; | |
| int query(int p) // responde quantos números maiores que p existem | |
| { | |
| int sum = 0; | |
| while(p <= maxv && p) | |
| { | |
| sum += bit[p]; | |
| p += (p & -p); | |
| } | |
| return sum; | |
| } | |
| int upd(int p, int val) // atualizo adicono val em p | |
| { | |
| while(p > 0) | |
| { | |
| bit[p] += val; | |
| p -= (p & -p); | |
| } | |
| } | |
| int main() | |
| { | |
| cin >> n >> q; | |
| for(int i = 1 ; i <= n ; ++i) cin >> v[i]; | |
| for(int i = 0 ; i < q ; ++i) | |
| { | |
| cin >> qr[i].l >> qr[i].r >> qr[i].y; // leio as perguntas de Sufia | |
| qr[i].id = i; | |
| qr[i].b = (qr[i].l/root); | |
| } | |
| // Algoritmo de Mo | |
| sort(qr, qr+q); // ordeno as perguntas | |
| int left = 0, right = 0; | |
| for(int i = 0 ; i < q ; ++i) | |
| { | |
| int l = qr[i].l; | |
| int r = qr[i].r; | |
| int y = qr[i].y; | |
| int id = qr[i].id; | |
| while(right < r) // a rua right esta no dentre do meu intervalo | |
| { | |
| right++; // aumento o intevalo | |
| upd(v[right], 1); // adiociono o prédio na bit | |
| } | |
| while(left > l) // a rua left esta no dentre do meu intervalo | |
| { | |
| left–; // aumento o intervallo | |
| upd(v[left], 1); // adiciono o prédio na bit | |
| } | |
| while(right > r) // a rua right não esta no dentre do meu intervalo | |
| { | |
| upd(v[right], -1); // removo o prédio na bit | |
| right–; // diminuo o intervalo | |
| } | |
| while(left < l) // a rua left não esta no dentre do meu intervalo | |
| { | |
| upd(v[left], -1); // removo o prédio na bit | |
| left++; // diminuo o intervalo | |
| } | |
| ans[id] = query(y+1); // consulto quantos prédio com altura maior que y existem entre as ruas l e r | |
| } | |
| for(int i = 0 ; i < q ; ++i) // imprimo as respostas | |
| { | |
| cout << ans[i] << "\n"; | |
| } | |
| } |
