KGSS  Maximum Sum
This will be indicated in the input by a 'U' followed by space and then two integers i and x.
U i x, 1 ≤ i ≤ N, and x, 0 ≤ x ≤ 10^8.
This operation sets the value of A[i] to x.
Query:This will be indicated in the input by a 'Q' followed by a single space and then two integers i and j.
Q x y, 1 ≤ x < y ≤ N.
You must find i and j such that x ≤ i, j ≤ y and i != j, such that the sum A[i]+A[j] is maximized. Print the sum A[i]+A[j].
Input
The first line of input consists of an integer N representing the length of the sequence. Next line consists of N space separated integers A[i]. Next line contains an integer Q, Q ≤ 10^5, representing the number of operations. Next Q lines contain the operations.
Output
Output the maximum sum mentioned above, in a separate line, for each Query.
Example
Input: 5 1 2 3 4 5 6 Q 2 4 Q 2 5 U 1 6 Q 1 5 U 1 7 Q 1 5 Output: 7 9 11 12
hide comments
iharsh234:
20160708 21:14:18
store max and its pos in a range.


lt:
20160707 12:13:24
Awesome! Ac in one shot :D 

Deepak :
20160630 13:54:19
AC on one go... i used N=100010 and for tree 4*N...easy Last edit: 20160630 13:54:34 

aryan_r:
20160625 16:57:22
There can be at most Q1 updates and last one might be a Query . So use N=2*10^5 :) else Run time error ! 

karthik1997:
20160530 06:58:28
Used array of size 2*10^5 and tree of size 520000 and got AC directly . Else you will get Runtime error... Good Luck :D ..Way to go segment trees ..... 

vijay kumar paliwal:
20160527 11:36:30
@Rajat Singh Size of seg tree can go upto 4N for an array of size N. 

man:
20160521 05:21:45
first easy one related to segment tree encountred.. 

nk17kumar:
20160421 20:57:10
yeaah ! 1st attempt AC :) 

Safayet Islam Anonno:
20160206 07:30:50
So easy, AC in 0th submission. YAAAAY 

anshal dwivedi:
20151225 09:30:52
Easy one ! Ac in on go.......... :) 
Added by:  Swarnaprakash 
Date:  20090110 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Kurukshetra 09 OPC 