Pishty and Triangles

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Pishty is a little boy who lives in Khust, an ancient town with a castle and smart bears. Right now, he wants you to help him with a programming problem.
You are given a sequence A_{1}, A_{2}, ..., A_{N} and Q queries. There are two types of queries:
 1 pos val — Set A_{pos} = val.
 2 l r — Find the maximum possible perimeter of a triangle with nonzero area whose sides are elements of the subsequence A_{l}, A_{l+1}, ..., A_{r}. Note that each element of the subsequence can only be used as the length of at most one side, i.e. the sides of each valid triangle must be elements A_{x}, A_{y}, A_{z}, where l ≤ x < y < z ≤ r.
For each query of the second type, compute the maximum possible perimeter or determine that no valid triangle exists.
Input
 The first line of the input contains two spaceseparated integers N and Q.
 The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}.
 Q lines follow. Each of these lines describes one query in the following format:
 1 pos val for a query of the first type
 2 l r for a query of the second type
Output
For each query of the second type, print a single line containing one integer — the maximum perimeter or 0 if no triangle can be formed.
Constraints
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{9} for each valid i
 1 ≤ val ≤ 10^{9}
 1 ≤ l ≤ r ≤ N
 1 ≤ pos ≤ N
Subtasks:
Subtask #1 (5 pts): 1 ≤ N, Q ≤ 100
Subtask #2 (25 pts): 1 ≤ N, Q ≤ 2000
Subtask #3 (70 pts): original constraints
Example
Input: 5 4 3 1 8 9 7 2 1 5 1 2 12 2 1 3 2 2 5 Output: 24 0 29
Explanation
The first query asks us to find the maximum perimeter of a triangle using some of the elements {3, 1, 8, 9, 7}. We can take the elements 7, 8, and 9 and construct a triangle using these three elements as side lengths. This triangle has perimeter 7 + 8 + 9 = 24, which is the maximum possible perimeter. Hence the answer is 24.
The second query asks us to change the second element to 12.
The third query asks us to find the maximum perimeter of a triangle using some of the elements {3, 12, 8}. These three elements do not form a triangle, hence the answer is 0.
The fourth query asks us to find the maximum perimeter of a triangle using some of the elements {12, 8, 9, 7}. We can take the elements 8, 9 and 12 and make a triangle using these three elements as side lengths. This triangle has perimeter 8 + 9 + 12 = 29, which is maximum possible. Hence the answer is 29.
Author:  fekete 
Editorial  https://discuss.codechef.com/problems/PSHTRG 
Tags  fekete, march18, medium, mergesort, segmenttree, triangle 
Date Added:  12122017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions