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].


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:
  1. Get the maximum sum subarray within a subarray [l; r].
  1. Update the array at position p with value x.


For each query of type 1, the program should print the answer to that query.


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


Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue