| Fişierul intrare/ieşire: | panamasum.in, panamasum.out | Sursă | IIOT 2022-23 Runda 1 |
| Autor | Stefan Dascalescu | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Panamasum
While their car was lost in Panama, Carlos and Pablo decided to have fun with some math. One day, Carlos came up with what he called a Panama sum.
Basically, a Panama sum is the sum of some values in an 1-indexed array, where the values on the odd positions are added to the sum and the values on the even positions are subtracted from the sum.
For example, the Panama sum of the array 10, 6, 9, 4, 2, 0 is 10 - 6 + 9 - 4 + 2 - 0 which is equal to 11
Because finding this is way too easy for Pablo (he is a programmer), he decided to make this challenge more difficult.
Therefore, he invented the maximum Panama sum, which is defined as the maximum Panama sum we can get if we select a non-empty subarray from a given array.
Now he wants Carlos to find this value for multiple queries which might involve changing some values as well.
Help Carlos get this problem done and he will take you for a ride once he finds his car!
Date de intrare
The first line of the input file panamasum.in consists of two integers, n and q.
The second line of the input consists of n integers, representing the initial array v.
The next q lines of the input contain the queries you are given.
On each line, you will get the description of a query, which can be of two types:
1 a b - the value on position a is changed to b.
2 l r - find the maximum Panama sum of the subarray l, r.
Date de ieşire
The output file panamasum.out will contain as many lines as queries of type 2 exist in the input (there is at least one query of type 2). Each line will contain the answer to a query, in the order they were given in the input.
Restricţii
- 1 ≤ n, q ≤ 10^5
- 0 ≤ v[i], b ≤ 10^9
- For tests worth 20 points, 1 ≤ n ≤ 100, 1 ≤ q ≤ 1000.
- For tests worth 20 more points, 1 ≤ n ≤ 5000, 1 ≤ q ≤ 5000.
Exemplu
| panamasum.in | panamasum.out |
|---|---|
| 10 6 5 9 1 2 3 4 6 4 2 8 2 3 7 2 4 10 2 6 9 1 5 8 2 1 10 2 4 6 | 6 10 6 10 8 |
