fork(4) download
  1. // Solução para o problema K do Aquecimento para a OBI 2015 do URI Online Judge.
  2. // Estrutura: Binary Indexed Tree (ou Fenwick Tree)
  3. // Complexidade: O(Q*log N), sendo Q o número de consultas
  4. #include <stdio.h>
  5. const int MAXN = 100100;
  6.  
  7. int n, vet[MAXN], BIT[MAXN];
  8. // Adiciona o valor v à posição idx do vetor
  9. void update(int idx, int v){
  10. while(idx<=n){
  11. BIT[idx]+=v;
  12. idx+=(idx&-idx);
  13. }
  14. }
  15. // Calcula a soma do vetor no intervalo [1,idx]
  16. int query(int idx){
  17. int sum = 0;
  18. while(idx>0){
  19. sum+=BIT[idx];
  20. idx-=(idx&-idx);
  21. }
  22. return sum;
  23. }
  24.  
  25. int main(){
  26. int x;
  27. char c;
  28.  
  29. scanf("%d", &n);
  30. for(int i = 1; i <= n; i++){
  31. scanf("%d", &vet[i]);
  32. // Adicionamos o valor lido na posição i
  33. update(i,vet[i]);
  34. }
  35. while(scanf(" %c", &c)!=EOF){
  36. scanf("%d", &x);
  37. // Para cada consulta do tipo 1, retiramos vet[x] da posição x
  38. if(c=='a') update(x,-vet[x]);
  39. // E para cada consulta do tipo 2, calculamos a soma do intervalo [1,x-1]
  40. else printf("%d\n", query(x-1));
  41. }
  42.  
  43. return 0;
  44. }
Success #stdin #stdout 0s 3468KB
stdin
10
1 2 3 4 5 4 3 2 1 2
a 9
? 10
a 2
a 5
? 6
a 6
? 10
stdout
24
8
13