// Solução para o problema K do Aquecimento para a OBI 2015 do URI Online Judge.
// Estrutura: Binary Indexed Tree (ou Fenwick Tree)
// Complexidade: O(Q*log N), sendo Q o número de consultas
#include <stdio.h>
const int MAXN = 100100;
int n, vet[MAXN], BIT[MAXN];
// Adiciona o valor v à posição idx do vetor
void update(int idx, int v){
while(idx<=n){
BIT[idx]+=v;
idx+=(idx&-idx);
}
}
// Calcula a soma do vetor no intervalo [1,idx]
int query(int idx){
int sum = 0;
while(idx>0){
sum+=BIT[idx];
idx-=(idx&-idx);
}
return sum;
}
int main(){
int x;
char c;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &vet[i]);
// Adicionamos o valor lido na posição i
update(i,vet[i]);
}
while(scanf(" %c", &c)!=EOF){
scanf("%d", &x);
// Para cada consulta do tipo 1, retiramos vet[x] da posição x
if(c=='a') update(x,-vet[x]);
// E para cada consulta do tipo 2, calculamos a soma do intervalo [1,x-1]
else printf("%d\n", query(x-1));
}
return 0;
}
Ly8gU29sdcOnw6NvIHBhcmEgbyBwcm9ibGVtYSBLIGRvIEFxdWVjaW1lbnRvIHBhcmEgYSBPQkkgMjAxNSBkbyBVUkkgT25saW5lIEp1ZGdlLgovLyBFc3RydXR1cmE6IEJpbmFyeSBJbmRleGVkIFRyZWUgKG91IEZlbndpY2sgVHJlZSkKLy8gQ29tcGxleGlkYWRlOiBPKFEqbG9nIE4pLCBzZW5kbyBRIG8gbsO6bWVybyBkZSBjb25zdWx0YXMKI2luY2x1ZGUgPHN0ZGlvLmg+CmNvbnN0IGludCBNQVhOID0gMTAwMTAwOwoKaW50IG4sIHZldFtNQVhOXSwgQklUW01BWE5dOwovLyBBZGljaW9uYSBvIHZhbG9yIHYgw6AgcG9zacOnw6NvIGlkeCBkbyB2ZXRvcgp2b2lkIHVwZGF0ZShpbnQgaWR4LCBpbnQgdil7CiAgICB3aGlsZShpZHg8PW4pewogICAgICAgIEJJVFtpZHhdKz12OwogICAgICAgIGlkeCs9KGlkeCYtaWR4KTsKICAgIH0KfQovLyBDYWxjdWxhIGEgc29tYSBkbyB2ZXRvciBubyBpbnRlcnZhbG8gWzEsaWR4XQppbnQgcXVlcnkoaW50IGlkeCl7CiAgICBpbnQgc3VtID0gMDsKICAgIHdoaWxlKGlkeD4wKXsKICAgICAgICBzdW0rPUJJVFtpZHhdOwogICAgICAgIGlkeC09KGlkeCYtaWR4KTsKICAgIH0KICAgIHJldHVybiBzdW07Cn0KCmludCBtYWluKCl7CiAgICBpbnQgeDsKICAgIGNoYXIgYzsKCiAgICBzY2FuZigiJWQiLCAmbik7CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKyl7CiAgICAgICAgc2NhbmYoIiVkIiwgJnZldFtpXSk7CiAgICAgICAgLy8gQWRpY2lvbmFtb3MgbyB2YWxvciBsaWRvIG5hIHBvc2nDp8OjbyBpCiAgICAgICAgdXBkYXRlKGksdmV0W2ldKTsKICAgIH0KICAgIHdoaWxlKHNjYW5mKCIgJWMiLCAmYykhPUVPRil7CiAgICAgICAgc2NhbmYoIiVkIiwgJngpOwogICAgICAgIC8vIFBhcmEgY2FkYSBjb25zdWx0YSBkbyB0aXBvIDEsIHJldGlyYW1vcyB2ZXRbeF0gZGEgcG9zacOnw6NvIHgKICAgICAgICBpZihjPT0nYScpIHVwZGF0ZSh4LC12ZXRbeF0pOwogICAgICAgIC8vIEUgcGFyYSBjYWRhIGNvbnN1bHRhIGRvIHRpcG8gMiwgY2FsY3VsYW1vcyBhIHNvbWEgZG8gaW50ZXJ2YWxvIFsxLHgtMV0KICAgICAgICBlbHNlIHByaW50ZigiJWRcbiIsIHF1ZXJ5KHgtMSkpOwogICAgfQoKICAgIHJldHVybiAwOwp9