You are given a sequence A[1], A[2], ..., A[N] ( 0 ≤ A[i] ≤ 10^8 , 2 ≤ N ≤ 10^5 ). There are two types of operations and they are defined as follows:
Update:
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
Warning: large Input/Output data, be careful with certain languages
|
|
|
|
<script language="JavaScript">
<!--
$(document).ready(function(){
$('.pager_link').bind('click', function(me){
var href=$(me.currentTarget).attr('href');
$('#ccontent').animate({opacity: 0.5},1);
$.ajax({
type: "GET",
url: href+",ajax=1",
contentType: "application/x-www-form-urlencoded;charset=ISO-8859-2",
success: function(data){
$('#ccontent').html(data);
$('#ccontent').animate({opacity: 1.0},1);
},
error: function(err){
alert('error');
}
});
return false;
});
});
-->
</script>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://CvEuApme.png">
</td>
<td class="comm comm_odd">
<a href="/users/zayady">zayady</a>:
<span style="font-size: 10px; color: #666;">2021-11-09 23:12:52</span>
<br>
<p>i solve it usint sqrt decom , and i got AC , but this test case breaked my solution ( corner case when the size of block is equal 1 )
the correct answer is 3 not 8
1
5
2
U 1 3
Q 1 1
Last edit: 2021-11-09 23:15:01
</td>
</tr></p>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://UUtRKwq0.png">
</td>
<td class="comm comm_even">
<a href="/users/fuadul_hasan">fuadul_hasan</a>:
<span style="font-size: 10px; color: #666;">2021-09-28 10:43:38</span>
<br>
<p>simple problem... best one for start learning segtree</p>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://076Rvqyb.png">
</td>
<td class="comm comm_odd">
<a href="/users/mortal_beast">mortal_beast</a>:
<span style="font-size: 10px; color: #666;">2021-06-06 15:17:15</span>
<br>
<p>Good for begineers</p>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://g4IF7Bph.png">
</td>
<td class="comm comm_even">
<a href="/users/rimuru_404">rimuru_404</a>:
<span style="font-size: 10px; color: #666;">2021-06-05 05:38:54</span>
<br>
<p>After some silly mistakes AC. Nice problem for segment tree beginners </p>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://7r2cbf8j.png">
</td>
<td class="comm comm_odd">
<a href="/users/mukund007">mukund007</a>:
<span style="font-size: 10px; color: #666;">2021-05-30 08:43:03</span>
<br>
<p>Fenwick Tree go go</p>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://cXSQQIhg.png">
</td>
<td class="comm comm_even">
<a href="/users/saurabh_kl">saurabh_kl</a>:
<span style="font-size: 10px; color: #666;">2021-02-11 21:05:39</span>
<br>
<p>Accepting Java solution, I don't know it gives TLE with Scanner or not but FastReader is okay</p>
<b>Last edit: 2021-02-11 21:06:32</b>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://zDex8ZMH.png">
</td>
<td class="comm comm_odd">
<a href="/users/kanisht09">kanisht09</a>:
<span style="font-size: 10px; color: #666;">2021-01-22 21:47:48</span>
<br>
<p>Solved it using segment trees 2 different ways</p>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://fkemj5ZV.png">
</td>
<td class="comm comm_even">
<a href="/users/saurav7192">saurav7192</a>:
<span style="font-size: 10px; color: #666;">2020-08-06 10:56:08</span>
<br>
<p>Aced finally..............................</p>
<b>Last edit: 2020-08-06 12:30:50</b>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://48y4QWPk.png">
</td>
<td class="comm comm_odd">
<a href="/users/skj_helloworld">skj_helloworld</a>:
<span style="font-size: 10px; color: #666;">2020-08-04 12:34:34</span>
<br>
<p>accepted in one go</p>
</td>
</tr>
<tr>
<td width="50" style="vertical-align:top;">
<img src="file://DGbopyJR.png">
</td>
<td class="comm comm_even">
<a href="/users/chefpr7">chefpr7</a>:
<span style="font-size: 10px; color: #666;">2020-07-02 09:09:33</span>
<br>
<p>AC in One Go!! Nice practice problem for newbies!</p>
</td>
</tr>
1. Don't post any source code here.
2. Please be careful, leave short comments only. Don't spam here.
3. For more discussion (hints, ideas, solutions) please visit our
4. Authors of the problems are allowed to delete the post and use html code here (e.g. to provide some useful links).
</td>
</tr>
