Comentário NOIC OBI 2015 - Fase 2 - Programação Nível 2

Comentário por Rogério Júnior

Para ver o caderno de tarefas da segunda fase da Programação Nível 2 da OBI 2015, clique aqui.

Macacos me mordam!

Conhecimento prévio necessário

Geometria Computacional (Produto vetorial)

O enunciado é uma adaptação simplificada do problema de encontrar o Fecho Convexo. A primeira coisa que devemos fazer é tratar os topos das árvores como pontos no plano cartesiano e salvá-los em um vetor de pontos de nome tree. Vamos representar um ponto como um par de inteiros e chamá-lo de dot. Essa estrutura terá dois membros: X e Y, que representam as coordenadas do ponto. Depois que salvarmos todos os pontos no vetor tree, vamos ordená-los pela coordenada X.

Observemos agora três árvores quaisquer (digamos A, B e C, nesta ordem) do percurso feito pelo macaco. Observe que se as três estão no percurso, então é impossível pular direto de A para C, ou seja, de A, não é possível ver C, pois B está no meio. Isso significa, explicitamente, que o ângulo (com direção cartesiana, ou seja, anti-horária) $\measuredangle{ABC}$ é convexo. Veja, lembrando que A, B e C estão ordenados por coordenada X:

$\measuredangle{ABC}$ côncavo: o macaco consegue pular de A para C

$\measuredangle{ABC}$ convexo: o macaco não consegue pular de A para C

Deste modo, dentre todas as árvores selecionadas, não pode haver três que formam um ângulo côncavo. Agora observe a seguinte propriedade: sejam A, B, C e D pontos ordenados pelo eixo X. Se $\measuredangle{ABC}$ é côncavo e $\measuredangle{ACD}$ também é côncavo, então $\measuredangle{ABD}$ é côncavo.

Observe, na figura acima, o polígono ABCD e seus respectivos ângulos internos $\hat{A}$ , $\hat{B}$ , $\hat{C}$ e $\hat{D}$ . Sabemos que:

$\hat{A}+\hat{B}+\hat{C}+\hat{D}=360^{\circ}$

Mas $\hat{C}>180^{\circ}\Rightarrow\hat{A}+\hat{B}+\hat{D}<180^{\circ}\Rightarrow\hat{B}<180^{\circ}$

Com isso, vamos olhar um a um os pontos ordenadamente. Guardaremos uma pilha que, ao final do algoritmo, será nosso caminho. Note que, pela definição que encontramos, estamos buscando a parte superior do fecho convexo dos pontos. Adicionaremos um a um todos os pontos à pilha. Entretanto, antes de adicionarmos um ponto, temos que garantir que ele não forma um ângulo côncavo com seus dois anteriores, removendo o último ponto da pilha enquanto o ângulo formado for côncavo. Quando enfim o novo ponto formar um ângulo convexo, o adicionamos ao topo da pilha.

Note que a propriedade mostrada acima garante que todos os pontos que foram tirados para que um determinado ponto C fosse inserido realmente não participam do fecho convexo, mesmo que posteriormente C seja retirado para inserirmos um ponto D.

O único problema que ainda falta resolvermos é como descobrir se o ângulo $\measuredangle{ABD}$ é côncavo ou convexo. Felizmente, produto vetorial transforma isso em uma tarefa muito fácil. Olhar o ângulo $\measuredangle{ABD}$ é o olhar o ângulo formado pelos vetores $(\vec{A}-\vec{B})$ e $(\vec{C}-\vec{B})$ , e sabemos que se este ângulo for côncavo, o produto $(\vec{A}-\vec{B})\times(\vec{C}-\vec{B})$ será negativo. Assim, para implementarmos a função chega que recebe três pontos A, B e C como parâmetros e retorna true se o macaco consegue pular de A para C sem parar em B, basta implementarmos o produto citado acima e verificarmos se ele é negativo.

No fim do algoritmo, teremos todas as árvores pelas quais o macaco passa. Para pular entre $x$ árvores, ele dá $x-1$ pulos, logo basta imprimirmos o número de árvores na pilha subtraído de uma unidade. Segue o código para melhor entendimento.

A complexidade é O(n og n) devido à ordenação dos pontos. Além disso, note que é muito importante o uso de long long por multiplicarmos números que podem ir até $10^9$ .

	// Macacos me mordam! - F2P2 - OBI 2015
	// Rogério Júnior
	// Complexidade: O(n log n)

	#include <cstdio> // printf e scanf
	#include <vector> // vector
	#include <algorithm> // sort

	using namespace std; // para uso do C++

	// por comodidade
	#define X first
	#define Y second

	typedef long long ll;
	typedef pair<ll,ll> dot;

	// declaro as variáveis que vou usar
	int n;
	vector<dot> pilha, tree;

	// função que checa se o ângulo ABC é côncavo
	bool chega(dot a, dot b, dot c){

	// declaro os vetores v1=A-B e v2=C-B
	dot v1=dot(a.X-b.X, a.Y-b.Y), v2=dot(c.X-b.X, c.Y-b.Y);

	// calculo o produto vetorial de v1 e v2
	ll cross_product = v1.Xv2.Y-v1.Yv2.X;

	// se o produto for não positivo, o ângulo é côncavo
	return cross_product<=0;
	}

	int main(){

	// leio o valor de n
	scanf("%d", &n);

	// para cada ponto da entrada
	for(int i=0; i<n; i++){

	// lendo suas coordenadas X e Y
	ll x, y;
	scanf("%lld %lld", &x, &y);

	// e o adiciono ao vetor tree
	tree.push_back(dot(x,y));
	}

	// ordeno os pontos por coordenada X
	sort(tree.begin(), tree.end());

	// percorro os pontos ordenadamente
	for(int i=0; i<n; i++){

	// chamo de p o ponto que estou olhando
	dot p=tree[i];

	// enquanto hoouver mais de um ponto na pilha
	while(pilha.size()>1){

	// vejo quem são os dois pontos do topo da pilha
	int last=pilha.size()-1, semi_last=pilha.size()-2;

	// se p formar um ângulo côncavo com os pontos do topo da pilha
	// significa que o macaco não precisa do ponto do meio para chegar a p
	// logo elimino o ponto do topo da pilha
	if(chega(pilha[semi_last], pilha[last], p)) pilha.pop_back();

	// caso contrário, ou seja, o ângulo seja convexo
	// não preciso mais tirar pontos e continuo o algoritmo
	else break;
	}

	// adiciono p à pilha e vou para a próxima iteração
	pilha.push_back(p);
	}

	// no fim, imprimo o número de elementos na pilha menos 1
	printf("%d\n", pilha.size()-1);

	return 0;
	}

view raw macacos.cpp hosted with

by GitHub

Chocolate em barra

Conhecimento prévio necessário:

Entrada e saída (Aula 1 do Curso Noic)
Estruturas condicionais (Aula 2 do Curso Noic)

Só há duas possibilidades de divisão do chocolate: dividi-lo verticalmente ou horizontalmente. Seja n o tamanho do lado do tabuleiro, x1 e y1 as coordenadas da primeira figurinha e x2 e y2 as coordenadas da segunda. Para que o tabuleiro seja divisível na horizontal, uma figurinha deve estar na metade superior e outra na inferior, ou seja: o menos dos y deve ser menor ou igual a n/2 e o maior deles maior que n/2. Em C, a condição ficaria "if(min(y1,y2)<=n/2 && max(y1,y2)>n/2)". De maneira análoga, para dividirmos verticalmente o tabuleiro, uma figurinha deve estar na esquerda e outra na direita, ou seja "if(min(x1,x2)<=n/2 && max(x1,x2)>n/2)". Se qualquer uma das duas condições citadas for atendida, podemos dividir o tabuleiro e devemos imprimir uma única linha com o caractere 'S'. Caso contrário, uma com o caractere 'N'. Segue o código para melhor entendimento:

	// Chocolate em barra - F2P2 - OBI 2015
	// Rogério Júnior
	// Complexidade: O(1)

	#include <cstdio> // scanf e printf
	#include <algorithm> // min e max

	using namespace std; // para uso do C++

	// declaro as variáveis que vou usar
	int n, x1, y1, x2, y2;

	int main(){

	// leio os valores das variáveis
	scanf("%d %d %d %d %d", &n, &x1, &y1, &x2, &y2);

	// checo se posso dividir verticalmente ou horizontalmente
	if((min(x1,x2)<=n/2 and max(x1,x2)>n/2) or (min(y1,y2)<=n/2 and max(y1, y2)>n/2))
	printf("S\n"); // se puder impimo o caractere 'S'

	else printf("N\n"); // se não, imprimo 'N'

	return 0;
	}

view raw chocolate.cpp hosted with

by GitHub

Mina

Conhecimento prévio necessário:

Menor caminho em grafos (Aula 10 do Curso Noic)
Heap (Aula 11 do Curso Noic)

O problema é uma aplicação direta do Algoritmo de Dijkstra. No algoritmo, a matriz que representa a mina será vista como um grafo em que cada casa é um vértice. Cada vértice estará ligado a todos os seus vizinho na matriz e o peso da aresta desta ligação será 1 ou 0, dependendo do valor de explorar este vizinho. A única diferença do algoritmo aqui mostrado para o da aula do Curso será que este vai rodar em O(E log V) (E é o número de arestas e V o de vértices) porque usaremos uma heap (priority_queue) para guardarmos os vértices mais próximos da origem durante a execução do Dijkstra. Note que, para guardarmos os vértices usaremos um par de inteiros (que chamaremos de ii). No caso, o par (i, j) faz referência à casa da linha i, coluna j. Veja o código:

	// Mina - F2P2 - OBI 2015
	// Rogério Júnior
	// Complexidade: O(n² log n)

	#include <cstdio> // scanf e printf
	#include <vector> // vector
	#include <queue> // priority_queue
	#include <algorithm> // min
	#include <cstring> // memset

	using namespace std; // para uso do C++

	// defino o valor de INF e MAXN
	#define MAXN 110
	#define INF 0x3f3f3f3f

	// por comodidade
	#define F first
	#define S second

	typedef pair<int,int> ii;
	typedef pair<int, ii> iii;

	// declaro as variáveis que vou usar
	int n, tab[MAXN][MAXN], dist[MAXN][MAXN];

	// Algoritmo de Dijkstra iterado na matriz
	int dijkstra(){

	// inicialize os valores padrões do algoritmo
	memset(dist, INF, sizeof(dist));

	// note que o quadrado inicial nunca está bloquado
	dist[1][1]=0;

	priority_queue< iii, vector<iii>, greater<iii> > heap;

	heap.push(iii(0, ii(1,1)));

	// enquanto a heap não estiver vazia
	while(!heap.empty()){

	// guarde o elemento do topo e o retire da heap
	int d=heap.top().F, i=heap.top().S.F, j=heap.top().S.S;

	heap.pop();

	// se o elemento já tiver sido processado,
	// vá para a próxima iteração do loop
	if(d>dist[i][j]) continue;

	// sejam i_ e j_ as coordenadas de um vizinho do elemento que estamos processando
	int i_=i+1, j_=j;

	// se ele estiver nos limites da matriz e encontrarmos um novo menor caminho para ele
	if(i_>=1 and i<=n and j>=1 and j<=n and dist[i][j]+tab[i_][j_]<dist[i_][j_]){

	// atualize a menor distância até ele e o reinsira na heap
	dist[i_][j_]=dist[i][j]+tab[i_][j_];
	heap.push(iii(dist[i_][j_], ii(i_,j_)));
	}

	// repita o processo com todos os vizinhos
	i_=i-1, j_=j;

	if(i_>=1 and i<=n and j>=1 and j<=n and dist[i][j]+tab[i_][j_]<dist[i_][j_]){

	dist[i_][j_]=dist[i][j]+tab[i_][j_];
	heap.push(iii(dist[i_][j_], ii(i_,j_)));
	}

	i_=i, j_=j+1;

	if(i_>=1 and i<=n and j>=1 and j<=n and dist[i][j]+tab[i_][j_]<dist[i_][j_]){

	dist[i_][j_]=dist[i][j]+tab[i_][j_];
	heap.push(iii(dist[i_][j_], ii(i_,j_)));
	}

	i_=i, j_=j-1;

	if(i_>=1 and i<=n and j>=1 and j<=n and dist[i][j]+tab[i_][j_]<dist[i_][j_]){

	dist[i_][j_]=dist[i][j]+tab[i_][j_];
	heap.push(iii(dist[i_][j_], ii(i_,j_)));
	}
	}

	// e retorne a distância até o quadrado inferior direito da matriz
	return dist[n][n];
	}

	int main(){

	// leia a entrada
	scanf("%d", &n);

	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++)
	scanf("%d", &tab[i][j]);

	// umprima o valor retornado pelo algoritmo de Dijkstra
	printf("%d\n", dijkstra());

	return 0;
	}

view raw mina.cpp hosted with

by GitHub

Cálculo

Conhecimento prévio necessário

Vetores (Aula 3 do Curso Noic)

Observe que a operação descrita no enunciado é extremamente parecida com uma soma normal de dois números binários, com apenas duas diferenças:

Os números são somados da esquerda para a direita (a primeira casa sempre representa $\frac{1}{2}$ )
Zeros à direita não têm valor (definição do enunciado)

Vamos explicar melhor estes dois detalhes. O primeiro significa que vamos somar, casa a casa, os números da esquerda para a direita, ao invés do padrão contrário que geralmente usamos em somas e subtrações. Isto ocorre porque agora a primeira casa tem um valor fixo, ao contrário de uma operação normal de adição onde a casa com valor fixo é a última (casa das unidades). O segundo detalhe vem de o enunciado falar para sempre usarmos o menor número de dígitos possível, logo, não há para que imprimirmos zeros à direita do número, pois 1010000, por exemplo, é o mesmo que 101. Agora, que sabemos disso, basta somarmos os números. Vamos usar três vetores de inteiros: o num1, num2 e resp. Os dois primeiros irão guardar os números que devemos somar, enquanto que resp guardará o resultado final. Usaremos um for para percorrermos e somarmos os dois números, guardando esta soma em resp. Feito isso, resp[i] será igual a num1[i]+num2[i] para todo i. Agora, vamos percorrer resp de trás para frente procurando por casas sobrecarregadas (posições que guardam valores maiores que 1). Se o valor de uma casa for maior que 1, devemos fazer como uma soma normal: subtrair 2 da casa (porque 2 é a base) e adicionar uma unidade à casa anterior. O enunciado garante que a primeira casa nunca estará sobrecarregada, pois o número é sempre menor que 1. Feito isso, basta descobrirmos onde está o último dígito da resposta que não é zero (podemos fazer isso com um for que percorre a resposta atualizando uma variável tam para a posição em que está toda vez que encontra um dígito não nulo) para só a imprimirmos até aí, evitando impressão de zeros à direita. Segue o código para melhor entendimento:

	// Cálculo - F2P2 - OBI 2015
	// Rogério Júnior
	// Complexidade: O(n)

	#include <cstdio> // printf e scanf
	#include <algorithm> // max

	using namespace std; // para uso do C++

	#define MAXN 1010 // defino o valor de MAXN

	// declaro as variáveis que vou usar
	int m, n, num1[MAXN], num2[MAXN], resp[MAXN], tam;

	int main(){

	// leio a entrada
	scanf("%d %d", &m, &n);

	for(int i=1; i<=m; i++) scanf("%d", &num1[i]);

	for(int i=1; i<=n; i++) scanf("%d", &num2[i]);

	// calculo a soma bruta dos números
	for(int i=1; i<=max(n,m); i++) resp[i]=num1[i]+num2[i];

	// para cada casa da resposta
	for(int i=max(n,m); i>0; i--)

	// se o algarismo nela guardado for maior que 1
	if(resp[i]>1){

	// retiro duas unidades dele e aumento 1 unidade na casa à esquerda
	resp[i]-=2;
	resp[i-1]++;
	}

	// descubro onde fica o último algarismo não nulo do número
	for(int i=1; i<=max(n,m); i++) if(resp[i]) tam=i;

	// e então o imprimo
	for(int i=1; i<=tam; i++) printf("%d ", resp[i]);

	// ao final, imprimo a quebra de linha
	printf("\n");

	return 0;
	}

view raw calculo.cpp hosted with

by GitHub

Fila

Conhecimento prévio necessário

Implementação e busca rápida em BIT (Binary Indexed Tree)
Implementação e busca rápida em Árvore de Segmentos

Este é com certeza um dos problemas mais difíceis que já caiu na P2 da OBI, por exigir um conhecimento bem alto de estruturas de dados, no caso, implementação e busca rápida em BIT e Árvore de Segmentos.

Primeiramente, vamos ler toda a entrada como um conjunto de operações dos tipos descritos no enunciado. Para isso, faremos com que a fila comece vazia e seu estado inicial será construído adicionando, um a um, todos os competidores em suas respectivas posições através da operação 0. Feito isso, haverá agora n+q operações (pois teremos que adicionar os n competidores iniciais). Guardaremos todas essas operações usando três vetores: t, p e x, que guardam os inteiros que descrevem uma operação, nesta ordem.

A principal dificuldade do problema é a dinamicidade da fila, visto que seu tamanho varia com o problema. Para driblarmos este problema, usaremos consulta offline, ou seja, iremos ler todas as operações para só então resolvermos o problema. Assim, imagine que a fila é estática e tem n+q posições. Nesta fila estática, a posição de cada competidor é sua posição final na fila do problema após todas as operações serem feitas, não a posição em que ele começa. Mas como descobrimos a posição final de cada competidor?

Para isso, usaremos um BIT. Ele terá n+q posições e representará o estado atual da fila. Seja pos(i) o número que está salvo na posição i do vetor que o BIT está representando. Neste caso, se pos(i) = 1, então o competidor que ocupa a posição i de nossa fila estática já está nela. Se pos(i) = 0, então tal competidor não está. A fim de descobrirmos a posição de cada competidor, iremos processar a entrada na ordem inversa. Note que o estado da fila após a última operação é ela cheia, logo, iremos percorrer o BIT fazendo cada uma de suas posições receber o número 1.

Agora, a ideia é percorrermos as operações fazendo com que, ao olharmos a operação i, o BIT represente o estado da fila logo após tal operação ter sido realizada. Como mostrado acimo, isso é verdade para a primeira iteração. Com a ajuda do BIT, é fácil descobrir as verdadeiras posições de cada elemento.

Suponha que estamos olhando a operação i. Se t[i]=0, então i é uma operação de inserção. Nesta operação, inserimos um competidor de altura h[i] na posição p[i]+1. Observando nossa fila estática, em que algumas posições ainda podem faltar, sabemos que o competidor que acaba de ser inserido é que é antecedido por exatamente p[i] competidores já inseridos. Como cada competidor que está na fila contribui com 1 para a soma da BIT, basta usarmos uma busca rápida na BIT para encontrarmos a última posição cuja soma de todos os termos até ela é exatamente p[i]. Seja p' tal posição. Sabemos então que p'+1 é a primeira posição cuja soma de todos os termos do BIT até ela (inclusive) é p[i]+1, logo p'+1 é a posição na fila estática (posição final) em que foi inserido o competidor na operação i. Sabemos disso, alteramos o valor de p[i] para p'+1. Além disso, para garantir que a BIT continuará representando a fila para operações que vieram antes de i (e que ainda serão processadas, pois lembre-se que as estamos lendo na ordem inversa), devemos tirar do BIT o elemento que a operação i insere, para que ele represente a fila exatamente após a operação que antecede i. Sabemos que este é o elemento da posição p[i] (pois a atualizamos), logo basta retirarmos uma unidade desta posição da BIT.

Se, por outro lado, o valor de t[i] for 1, então a operação i é uma operação de busca. Porém, precisamos saber qual a posição na fila estática do competidor que usaremos como referência para nossa busca. Para tal, de maneira análoga ao outro tipo de operação, basta vermos qual a última posição da BIT cuja soma até ela é p[i] e adicionarmos 1, atualizando o valor de p[i] para esta posição.

Agora, sabemos a posição final de cada elemento usado por cada operação da entrada, o que facilita toda a solução do nosso problema. Iremos representar nossa fila estática por uma árvore de segmentos de máximo. Note que o BIT agora está completamente zerado, pois após termos processado todas as operações de inserção no passo anterior, todos os elementos terão sido retirados. O BIT agora continuará representando nossa fila, juntamente com a árvore de segmentos, para sabermos que elementos já estão em suas posições.

Dito isso, basta agora realizarmos as operações na ordem em que elas aparecem. Suponha que estamos processando a operação i. Se ela for do tipo 0, é fácil: inserimos o número h[i] na posição p[i] da árvore de segmentos, e adicionamos 1 à posição p[i] do BIT, pois agora p[i] representa a posição a qual cada operação se refere na nossa fila estática. Além disso, usaremos o vetor h para guardarmos que o elemento da posição p[i] tem altura x[i] ("h[p[i]]=x[i];"). Por outro lado, se a operação for do tipo 1, precisamos encontrar o elemento mais à direita da fila que não está após p[i] mas é maior que o elemento da posição p[i] por mais que x[i]. Seja h' a altura que tal elemento deve superar. A altura do elemento da posição p[i] é h[p[i]], logo h'=h[p[i]]+x[i]. Sabendo disso, basta procurarmos de maneira rápida na árvore de segmentos por este elemento com altura maior que h'. Precisamos então encontrar a posição p' do elemento mais a direita da fila que não está depois de p[i] e supera h': basta usarmos uma busca binária na árvore! Note que as posições vazias de elementos não inseridos não irão interferir na busca pois guardam o valor 0. Encontrada p', precisamos imprimir a posição atual na fila do elemento que está nessa posição, ou seja, contar quantos elementos estão atrás dele, mais ele. Para isso, basta imprimirmos a soma do BIT até a posição p', pois cada elemento contribui com 1 na soma.

Este comentário não tem como objetivo ser uma aula sobre buscas binárias em árvore de segmento e BIT, visto que estes foram apresentados como conhecimentos prévios necessários para que você entenda a solução do problema. O link apresentado para SegTree é uma introdução a esta estrutura de dados, mas o site fornecido apresenta muito mais aprofundamento sobre ela se você continuar lendo seus artigos sobre o assunto. Deste modo, o que farei será uma breve explicação da implementação das operações com estas estruturas, embutidas no próprio código que segue abaixo, mas é altamente recomendável que você leia as páginas citadas se não conhece as estruturas ou as operações:

	// Fila - F2P2 - OBI 2015
	// Rogério Júnior
	// Complexidade: O(n log n)

	#include <cstdio> // scanf e printf
	#include <algorithm> // max

	using namespace std; // para uso do C++

	#define MAXN 1200200 // observe que MAXN é em função de n+q

	// declaro as variáveis que vou usar
	int n, q, h[MAXN], t[MAXN], p[MAXN], x[MAXN], bit[MAXN], val[4*MAXN];

	// operação que retorna a soma de todos os elementos do BIT até a posição p
	int bit_sum(int p){

	// resp começa com valor 0
	int resp=0;

	// para cada posição da BIT que tem responsabilidade por casas de 1 a p
	// somo seu valor a resp e vou para a casa que se responsabiliza pela
	// primeira posição que ainda não somei
	for(; p>0; p-=p&-p) resp+=bit[p];

	// retorno o valor de resp
	return resp;
	}

	// operaçao que soma x à posição p do BIT
	void upd_bit(int p, int x){

	// adiciono x a toda posição que se responsabiliza por p
	for(;p<=n+q; p+=p&-p) bit[p]+=x;
	}

	// operação que retorna a última posição da BIT cuja soma até ela é x
	int busca_bit(int x){

	// resp começa com valor zero
	int resp=0;

	// analisarei todas as potências de 2 que podem estar na resposta
	// da maior par a a menor
	for(int i=30; i>=0; i--){

	// pot recebe o valor de 2^i
	int pot=(1<<i);

	// davez recebe resp atual mais a potência de 2 que estou testando
	int davez=resp+pot;

	// se davez superar o tamanho do BIT, ignoro pot
	if(davez>n+q) continue;

	// se, porém, a posição davez do BIT se responsabiliza por uma soma
	// menor que a procuramos, então pot está na resp
	if(bit[davez]<=x){

	// logo, procuramos agora apenas pela soma x-bit[davez]
	x-=bit[davez];

	// e incluo pot em resp
	resp=davez;
	}
	}

	// se x=0, então realmente encontramos uma posição do BIT
	// cuja soma era o valor original de x
	// logo retorno resp
	if (x==0) return resp;

	// caso contrário, retorno -1 para representar que tal posição não existe
	// este passo é mera formalidade
	return -1;
	}

	// opeação que faz a posição p da seg receber o valor x
	// seg é o número do segmento em que estamos
	// e ini e fim são, respectivamente, seu início e fim
	void upd_seg(int p, int x, int seg=1, int ini=1, int fim=n+q){

	// se estamos em um segmento da árvore que não inclui p
	// não há nada a fazer, e retornamos a função
	if(p<ini or p>fim) return;

	// se chegamos em um segmento que só tem um elemento
	// então este segmento so representa a posição p
	if(ini==fim){

	// logo seu valor recebe x
	val[seg]=x;

	// e retornamos a função
	return;
	}

	// se, porém, não chegamos a uma folha

	// meio recebe (ini+fim)/2
	int meio=(ini+fim)/2;

	// chamamos a função para os filhos esquerdo e direito
	// note que, da maneira que construo a árvore,
	// o filho esquerdo vai de ini a meio
	// e o direito vai de meio+1 a fim
	upd_seg(p, x, 2*seg, ini, meio);
	upd_seg(p, x, 2*seg+1, meio+1, fim);

	// e atualizamos o vamor do elemento máximo do segmento
	// para o máximo entre seus dois filho
	val[seg]=max(val[2seg], val[2seg+1]);
	}

	// função que retorna o elemento mais a direita do segmento
	// que não está após p e supera o valor de x
	// seg é o número do segmento em que estamos
	// e ini e fim são, respectivamente, seu início e fim
	int busca_seg(int p, int x, int seg=1, int ini=1, int fim=n+q){

	// se o maior valor no segmento não supera x, o elemento procurado
	// não está neste seguimento, e retornamos o elemento neutro
	if(val[seg]<=x) return 0;

	// se o segmento é inteiramente após p, então o elemento procurado
	// também não está neste segmento, logo retornamos o elemento neutro
	if(ini>p) return 0;

	// se o segmento só tem um elemento, retornamos ele
	// (veja a definição desta função no comentário que precede sua declaração)
	if(ini==fim) return ini;

	// meio recebe (ini+fim)/2
	int meio=(ini+fim)/2;

	// se o segmento termina depois de p, então usaremos o maior (mais à direita)
	// dentre os valores retornados por seus filhos
	if(fim>p) return max(busca_seg(p,x,2seg,ini,meio), busca_seg(p,x,2seg+1,meio+1,fim));

	//caso o segmento inteiro esteja dentro de um intervalo válido
	// iremos procurar por seu valor mais à direita que supera x

	// como procuramos pelo valor mais a direita, checamos primeiro o filho direito:
	// se ele tiver algum elemento maior que x, retornamos o seu elemento mais à direita que supera x
	if(val[2seg+1]>x) return busca_seg(p,x,2seg+1, meio+1, fim);

	// caso o filho direito não tenha tal elemento
	// retornamos o elemento mais a direita do filho esquerdo que supera x
	return busca_seg(p,x,2*seg,ini,meio);
	}

	int main(){

	scanf("%d", &n);

	// transformo o estado inicial da fila em queries de inserção
	for(int i=0; i<n; i++){

	p[i]=i;

	scanf("%d", &x[i]);
	}

	// leio todas as queries
	scanf("%d", &q);

	for(int i=n; i<n+q; i++) scanf("%d %d %d", &t[i], &p[i], &x[i]);

	// preencho toda a BIT
	for(int i=1; i<=n+q; i++) upd_bit(i, 1);

	// descbro as verdadeiras posições de cada query,
	// pré-processando-as na ordem inversa
	for(int i=n+q-1; i>=0; i--){

	// se for uma query de inserção
	if(t[i]==0){

	// descubro e atualizo a posição do elemento
	p[i]=busca_bit(p[i])+1;

	// e retiro o elemento da fila
	upd_bit(p[i], -1);
	}

	// se for uma query de pergunta,
	// apenas descubro e atualizo a posição do elemento
	else p[i]=busca_bit(p[i]-1)+1;
	}

	// agora, respondo as queries
	for(int i=0; i<n+q; i++){

	// se for uma query de inserção
	if(t[i]==0){

	//insiro o elemento na fila
	h[p[i]]=x[i];

	upd_seg(p[i], h[p[i]]);

	upd_bit(p[i], 1);
	}

	// se for uma query de pergunta,
	// apenas imprimo a resposta
	else printf("%d\n", bit_sum(busca_seg(p[i], h[p[i]]+x[i])));
	}

	return 0;
	}

view raw fila.cpp hosted with

by GitHub

Se você ainda tiver alguma dúvida em algum dos problemas, vá para a página inicial do Curso Noic de Informática e preencha o formulário para nos enviar sua dúvida.