Hydra Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Arranha-céu ======


//Nome do arquivo: arranhaceu.x, onde x deve ser c, cpp, java, js ou py//\\
//Fonte: [[https://olimpiada.ic.unicamp.br/pratique/ps/2017/f3/arranhaceu/]]//

Um arranha-céu residencial possui N andares, numerados de 1 a N. O síndico do arranha-céu está tendo muito trabalho com uma nova regra do corpo de bombeiros. Ele não sabe o porquê, mas os bombeiros apontam um andar k e exigem que o síndico informe o total de pessoas que moram no arranha-céu do andar 1 até o andar k, inclusive. Talvez seja alguma medida de segurança dos bombeiros! O problema é que o prédio tem muitos andares e toda hora tem gente se mudando, passando a morar no arranha-céu, ou indo embora. O síndico precisa cuidar de dois eventos:

    * Mudança: alterar o número de pessoas que moram num determinado andar;
    * Bombeiro: informar o total de pessoas que moram do andar 1 até um determinado andar, inclusive. 

Dados o número de pessoas que moram em cada andar do arranha-céu inicialmente, e uma sequência de eventos (do tipo Mudança ou Bombeiro), seu programa deve imprimir, para cada evento do tipo Bombeiro, o total de pessoas exigido, no momento do evento!

===== Entrada =====

A primeira linha da entrada contém dois inteiros N e Q, representando, respectivamente, o número de andares e o número de eventos. A segunda linha contém N inteiros Ai, 1 ≤ i ≤ N, indicando o número de pessoas que moram no i-ésimo andar inicialmente. Cada uma das Q linhas seguintes representa um evento e tem uma de duas formas:

    * "0 K P", Mudança, alterar o número de pessoas que moram no K-ésimo andar para P pessoas;
    * "1 K", Bombeiro, informar o total de pessoas que moram do andar 1 até o andar K, inclusive. 
 
===== Saída =====

Para cada evento do tipo Bombeiro, seu programa deve imprimir uma linha contendo um inteiro representando o total de pessoas correspondente aquele evento.

===== Restrições =====


  * 1 ≤ N ≤ 105 e 1 ≤ Q ≤ N
  * Há pelo menos um evento do tipo Bombeiro.
  * 1 ≤ K ≤ N
  * 0 ≤ Ai ≤ 1000 e 0 ≤ P ≤ 1000 

===== Informações sobre a pontuação =====

Em um conjunto de casos de teste somando 20 pontos, N ≤ 20000 

===== Exemplos =====

^ Entrada ^ Saída ^
| 8 4 | 84 |
| 30 2 0 42 10 11 11 9 | 54 |
| 1 5 | 30 |
| 0 4 12 | |
| 1 5 | |
| 1 1 | |
 
^ Entrada ^ Saída ^
| 1 1 | 0 |
| 0 | |
| 1 1 | |