Seletiva IOI 2014

intervalo.cpp

// Ivan Carvalho
// Intervalo - Seletiva IOI - OBI 2014
#include <bits/stdc++.h>
#define MAXN 200010
#define LSOne(S) (S&(-S))
using namespace std;
typedef long long ll;
ll bit[MAXN];
int freq[MAXN],acao[MAXN],vetor1[MAXN],vetor2[MAXN],n,q;
void atualiza_freq(int pos,int val){
	while(pos <= n+q){
		freq[pos]+= val;
		pos += LSOne(pos);
	}
}
void atualiza_bit(int pos,int val){
	ll convertido = ll(val);
	while(pos <= n+q){
		bit[pos] += convertido;
		pos += LSOne(pos);
	}
}
int sum_freq(int pos){
	int answer = 0;
	while(pos > 0){
		answer += freq[pos];
		pos -= LSOne(pos);
	}
	return answer;
}
ll sum_bit(int pos){
	ll answer = 0;
	while(pos > 0){
		answer += bit[pos];
		pos -= LSOne(pos);
	}
	return answer;
}
int find(int val){
	int ini = 1, fim = n+q,meio,resp;
	while(ini <= fim){
		meio = (ini+fim)/2;
		int temp = sum_freq(meio);
		if (temp >= val){
			resp = meio;
			fim = meio - 1;
		}
		else ini = meio + 1;
	}
	return resp;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&vetor2[i]);
		vetor1[i] = i;
	}
	scanf("%d",&q);
	for(int i=1;i<=n+q;i++) atualiza_freq(i,1);
	for(int i=n+1;i<=n+q;i++){
		getchar();
		char davez;
		scanf("%c",&davez);
		if (davez == 'I'){
			scanf("%d %d",&vetor1[i],&vetor2[i]);
			vetor1[i]++;
		}
		if (davez == 'S'){
			scanf("%d %d",&vetor1[i],&vetor2[i]);
			acao[i] = 1;
		}
	}
	for(int i=n+q;i>0;i--){
		if (acao[i] == 1){
			//printf("Antes : V1 %d V2 %d\n",vetor1[i],vetor2[i]);
			vetor1[i] = find(vetor1[i]);
			vetor2[i] = find(vetor2[i]);
			//printf("Depois : V1 %d V2 %d\n",vetor1[i],vetor2[i]);
		}
		else{
			vetor1[i] = find(vetor1[i]);
			atualiza_freq(vetor1[i],-1);
		}
	}
	for(int i=1;i<=n+q;i++){
		if (acao[i] == 1) printf("%lld\n",sum_bit(vetor2[i])-sum_bit(vetor1[i]-1));
		else{
			atualiza_bit(vetor1[i],vetor2[i]);
		}
	}
	//for(int i=1;i<=n+q;i++) printf("%lld ",sum_bit(i)-sum_bit(i-1));
	return 0;
}