Soma Alternada
Você tem um array de
n inteiros e q consultas. Existem dois tipos de consulta: atualizar o array em um índice específico p e calcular a soma alternada de um subarray [l; r].A soma alternada de um subarray
[l; r] é definida como a soma dos elementos em índices pares menos a soma dos elementos em índices ímpares dentro desse subarray. Em outras palavras, se o subarray [l; r] tiver os elementos , então a soma alternada é dada por .Para cada consulta do tipo 2, é necessário calcular e imprimir a soma alternada do subarray
[l; r] informado.Entrada
A primeira linha contém dois inteiros
n e q, que representam o tamanho do array e a quantidade de consultas, respectivamente (1 ≤ n, q ≤ ).
A segunda linha contém n inteiros separados por espaço (1 ≤ ≤ ), que são os elementos do array.
Cada uma das próximas q linhas representa uma consulta e está no formato 1 l r ou 2 p x, onde 1 indica uma consulta para calcular a soma alternada do subarray [l; r], e 2 indica uma atualização do valor em p para x (1 ≤ p ≤ n, 1 ≤ x ≤ , 1 ≤ l ≤ r ≤ n).Saída
Para cada consulta do tipo 2, imprima a soma alternada calculada em uma linha separada.
Exemplos
Entrada | Saída |
8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8 | 4
-9 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB