Seletiva IOI 2014

intervalo_treap.cpp

// Ivan Carvalho
// Intervalo - Seletiva IOI - OBI 2014
// Alternative solution : O(n*lg(n))
#include <bits/stdc++.h>
using namespace std;
typedef struct node* pnode;
typedef long long ll;
struct node{
	pnode l,r;
	ll puro,total;
	int prior,size;
	node(ll puro) : puro(puro),total(puro),prior(rand()),size(1),l(NULL),r(NULL){}
};
inline int sz(pnode t){return (t == NULL) ? 0 : t->size;}
inline void upd_sz(pnode t){if(t) t->size = sz(t->l) + 1 + sz(t->r);}
inline ll tot(pnode t){return (t == NULL) ? 0 : t->total;}
inline void operation(pnode t){if(t) t->total = tot(t->l) + t->puro + tot(t->r);}
void split(pnode t,int key,int add,pnode &l,pnode &r){
	if(t == NULL){
		l = r = NULL;
	}
	else{
		int cur_key = add + sz(t->l) + 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,ll 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(t,key,sz(L),mid,R);
	merge(t,L,R);
}
ll query(pnode t,int a,int b){
	pnode L,mid,R;
	split(t,a-1,0,L,R);
	split(R,b,sz(L),mid,R);
	ll resp = tot(mid);
	merge(t,L,mid);
	merge(t,t,R);
	return resp;
}
int main(){
	int n;
	scanf("%d",&n);
	pnode raiz = NULL;
	for(int i=1;i<=n;i++){
		ll davez;
		scanf("%lld",&davez);
		insert(raiz,i,davez);
	}
	int q;
	scanf("%d",&q);
	while(q--){
		char op;
		scanf(" %c",&op);
		if(op == 'I'){
			int pos;
			ll val;
			scanf("%d %lld",&pos,&val);
			insert(raiz,pos+1,val);
		}
		else{
			int a,b;
			scanf("%d %d",&a,&b);
			printf("%lld\n",query(raiz,a,b));
		}
	}
	return 0;
}