7394: CF EDU - Segment Tree P1 - Step 2 - A. Segment with the Maximum Sum
[Creator : ]
Description
In this problem, you need to write a segment tree to find the segment with the maximum sum.
Input
The first line contains two numbers $n,m\ (1≤n,m≤100,000)$, the size of the array and the number of operations.
The next line contains nn numbers $a_i$, the initial state of the array $-10^9≤a_i≤10^9$.
The following lines contain the description of the operations.
The description of each operation is as follows: i v, assign the value $v$ to the element with index $i\ 0≤i<n,\ -10^9≤v≤10^9$.
The next line contains nn numbers $a_i$, the initial state of the array $-10^9≤a_i≤10^9$.
The following lines contain the desc
The desc
Output
Print m+1 lines: the maximum sum of numbers on a segment before all operations and after each operation.
Please note that this segment may be empty (so the sum on it will be equal to 0).
Please note that this segment may be empty (so the sum on it will be equal to 0).
Sample 1 Input
5 2
5 -4 4 3 -5
4 3
3 -1
Sample 1 Output
8
11
7
Sample 2 Input
4 2
-2 -1 -5 -4
1 3
3 2
Sample 2 Output
0
3
3