Somma Alternata
Si dispone di un array di
n interi e di q interrogazioni. Esistono due tipi di interrogazioni: aggiornare l’array in un determinato indice p, oppure calcolare la somma alternata di una sottosequenza [l; r].La somma alternata di una sottosequenza
[l; r] è definita come la somma degli elementi in posizioni pari, sottratta di quelli in posizioni dispari all’interno di [l; r]. In altre parole, se la sottosequenza [l; r] contiene gli elementi , la somma alternata è .Per ogni interrogazione di tipo 2, occorre calcolare e stampare la somma alternata della sottosequenza
[l; r] specificata.Input
La prima riga contiene due interi
n e q, che rappresentano la dimensione dell’array e il numero di interrogazioni (1 ≤ n, q ≤ ).Output
Per ogni interrogazione di tipo 1 (ossia quella che calcola la somma alternata), è necessario stampare il risultato corrispondente in una nuova riga.
Esempi
Ingresso | Uscita |
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