Solução OBI 2015

fila.cpp

// Ivan Carvalho
// Fila - Fase 2 Programação Nível 2 - OBI 2015
// O(n*log(n))
#include <bits/stdc++.h>
using namespace std;
typedef struct node* pnode;
struct node{
	int prior,size,puro,maximo;
	pnode l,r;
	node(int puro) : l(NULL),r(NULL),puro(puro),maximo(puro),size(1), prior(rand()) {}
};
int sz(pnode t){
	if(t == NULL) return 0;
	return t->size;
}
int mx(pnode t){
	if(t == NULL) return -1;
	return t->maximo;
}
void upd_sz(pnode t){
	if(t == NULL) return;
	t->size = sz(t->l) + sz(t->r) + 1;
}
void operation(pnode t){
	if(t == NULL) return;
	t->maximo = max(max(mx(t->l),mx(t->r)),t->puro);
}
void split(pnode t,int key,int add,pnode &l,pnode &r){
	if(t == NULL){
		l = r = NULL;
	}
	else{
		int cur_key = sz(t->l) + add + 1;
		if(key < cur_key){
			split(t->l,key,add,l,t->l);
			r = t;
		}
		else{
			split(t->r,key,add + sz(t->l) + 1,t->r,r);
			l = t;
		}
	}
	upd_sz(t);
	operation(t);
}
void merge(pnode &t,pnode l,pnode r){
	if(l == NULL){
		t = r;
	}
	else if(r == NULL){
		t = l;
	}
	else if(l->prior > r->prior){
		merge(l->r,l->r,r);
		t = l;
	}
	else{
		merge(r->l,l,r->l);
		t = r;
	}
	upd_sz(t);
	operation(t);
}
void insert(pnode &t,int key,int val){
	pnode L,R;
	pnode aux = new node(val);
	split(t,key-1,0,L,R);
	merge(t,L,aux);
	merge(t,t,R);
}
void erase(pnode &t,int key){
	pnode L,mid,R;
	split(t,key-1,0,L,R);
	split(R,key,sz(L),mid,R);
	merge(t,L,R);
}
int find(pnode t,int key,int add){
	int cur_key = sz(t->l) + add + 1;
	if(key == cur_key) return t->puro;
	else if(key < cur_key) return find(t->l,key,add);
	else return find(t->r,key,add + sz(t->l) + 1);
}
int binary_search(pnode t,int add,int val){
	int cur_key = sz(t->l) + add + 1;
	if(mx(t->r) > val){
		return binary_search(t->r,add + sz(t->l) + 1,val);
	}
	if(t->puro > val) return cur_key;
	if(mx(t->l) > val) return binary_search(t->l,add,val);
	return 0;
}
int query(pnode &t,int a,int b,int val){
	if(a > b) return 0;
	pnode L,R;
	split(t,a-1,0,L,R);
	split(R,b,sz(L),t,R);
	int resp = binary_search(t,sz(L),val);
	merge(t,L,t);
	merge(t,t,R);
	return resp;
}
int main(){
	int N,Q;
	scanf("%d",&N);
	pnode raiz = NULL;
	for(int i=1;i<=N;i++){
		int davez;
		scanf("%d",&davez);
		insert(raiz,i,davez);
	}
	scanf("%d",&Q);
	while(Q--){
		int op;
		scanf("%d",&op);
		if(op == 0){
			int pos,altura;
			scanf("%d %d",&pos,&altura);
			insert(raiz,pos+1,altura);
		}
		else{
			int pos,altura;
			scanf("%d %d",&pos,&altura);
			printf("%d\n",query(raiz,1,pos-1,find(raiz,pos,0) + altura));
		}	
	}
	return 0;
}