Maximum Sum Subarray
You are given an array of
n integers and q queries. There are two types of queries: update array at a given index p, and calculate the maximum sum subarray within a subarray [l; r].The maximum sum subarray within a subarray
[l; r] is defined as the contiguous subarray with the maximum sum of its elements. In other words, you need to find the sum of the subarray [l'; r'] such that the sum of its elements is maximum among all possible non-empty subarrays within the range [l; r].Input
The first line of the input contains two integers
n and q (1 ≤ n, q ≤ 100 000).The next line contains
n space-separated integers The following
q lines contain all the queries - 1 l r (1 ≤ l ≤ r ≤ n) or 2 p x (1 ≤ p ≤ n, ≤ x ≤ ) representing the two types of queries:- Get the maximum sum subarray within a subarray
[l; r].
- Update the array at position
pwith valuex.
Output
For each query of type 1, the program should print the answer to that query.
Examples
Input | Output |
8 4
-2 1 -3 4 -7 2 1 -5
1 2 6
2 5 0
1 2 6
1 1 2 | 4
6
1 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB