collectmushrooms

Problem Description

Peanut owns a mushroom farm and wants to collect some mushrooms. His mushroom farm has N mushrooms in a row, numbered 0 to N-1 from left to right. Each mushroom i has deliciousness Di. Some mushrooms can be rotten, and so can have negative deliciousness. He assigns M minions to help him collect some mushrooms. Each minion i will be assigned a range A to B. Minions tend to fight each other, so Peanut will assign them ranges which do not intersect. However, each minion can only carry at most 1 mushroom, since they have small hands.

Also, minions sometimes rebel and decide to enhance or damage a mushroom. When this happens, the quality of mushroom at X will change to Y.

Help Peanut find the maximum deliciousness each minion can collect. Minions that are collecting mushrooms have to collect 1 mushroom.

Input

The first line contains the number N and M.

The second line contains N numbers, representing the array D.

M lines will follow. The first character of each line will be T.

If T is 0, then it represents a query. 2 integers will then follow, A and B.

If T is 1, then it represents a update. 2 integers will then follow, X, Y.

Output

For each line of query, you are to output the maximum deliciousness of mushrooms collected on a single line.

Limits

For all subtasks: 0 ≤ A≤ B< N, 0 ≤ X < N, |Di, Y| ≤ 109, 0 ≤ T ≤ 1

Subtask 1 (18%): 1 ≤ N, M ≤ 500000, T = 0. There will be no updates. Di = i for all i.

Subtask 2 (29%): 1 ≤ N, M ≤ 500000, T = 0. There will be no updates.

Subtask 3 (53%): 1 ≤ N, M ≤ 500000.

Subtask 4 (0%): Sample Testcases.

Sample Input 1

5 4
3 1 4 2 5
0 0 1
1 1 -3
1 3 6
0 2 4

Sample Output 1

3
6

Explanation

Farm has initial mushroom values: 3 1 4 2 5
Minion picks mushroom at position 0.
Minion damages mushroom 1. Farm has mushrooms values: 3 -3 4 2 5
Minion enhances mushroom 3. Farm has mushroom values: 3 -3 4 6 5
Minion picks mushroom at position 3.


Submitting to 'collectmushrooms'


You're not logged in! Click here to login


Submitting .cpp to 'collectmushrooms'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 0.5 Seconds
Memory Limit: 256MB
No. of ACs: 75
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 18
2 29
3 53
4 0