Solução Informática Avançado - Semana 62

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";
	}
	}

view raw

noic-solucao-avancado-s62.cpp

hosted with ❤ by GitHub