- Time limit: 1.00 s
- Memory limit: 512 MB
There is an array consisting of n integers. Some values of the array will be updated, and after each update, your task is to report the maximum subarray sum in the array.
The first input line contains integers n and m: the size of the array and the number of updates. The array is indexed 1,2,\ldots,n.
The next line has n integers: x_1,x_2,\ldots,x_n: the initial contents of the array.
Then there are m lines describing the changes. Each line has two integers k and x: the value at position k becomes x.
After each update, print the maximum subarray sum. Empty subarrays (with sum 0) are allowed.
- 1 \le n, m \le 2 \cdot 10^5
- -10^9 \le x_i \le 10^9
- 1 \le k \le n
- -10^9 \le x \le 10^9
5 3 1 2 -3 5 -1 2 6 3 1 2 -2
9 13 6