COURAGE  Living with Courage
Courage (the cowardly dog) lives with his master Muriel and her husband Eustace in the city of Nowhere. Eustace is a farmer but not a very good one. One fine day Courage was taking a stroll in Eustace's cropless field when he found seeds of a magical tree. He seow them in the field and the next morning n magical apple trees grew on the previously cropless field. The number of apples on the ith tree is apples[i] (0<=i< n). The number of apples on a tree may change as sometimes courage eats some apples from a tree and sometimes apples grow instantly on the trees (because they are MAGICAL!!).
Eustace wants to start a business of apples. So he frequently enquires Courage about the total number of apples present on a range of trees. A range of trees is denoted by two integers, l and r (0<=l<=r< n) and includes the trees from l to r (both inclusive).
Courage is very loyal to Muriel and wants to keep some apples for her. So whenever Eustace asks about the total number of apples on a range, he deliberately doesn't count the apples on a tree, s, such that l<=s<=r and MIN(apples[l],apples[l+1],apples[l+2],...,apples[r])=apples[s].
In other words, while calculating the sum of apples on the trees in a range, Courage doesn't include the apples on the tree that has the minimum number of apples in that range.
Input:
The first line contains n, the number of magical trees.
The second line contains n nonnegative integers that denote the array apples.
The third line contains a non negative integer p, which is the number of events that take place.
Now follow p lines. Each line will be of the form 'EAT x y' or 'GROW x y' or 'COUNT x y'.
'EAT x y' means that Courage ate x apples from the yth tree. (0<=y< n)
'GROW x y' means that x apples grew magically on the yth tree (0<=y< n).
And 'COUNT l r' means that Eustace has told Courage to count the number of apples on the range of trees from l to r, both inclusive.
Remember that the trees are indexed from 0.
Output:
For each 'COUNT x y' event, output a single number that Courage tells to Eustace.
Constraints:
1<=n<=100000
1<=p<=100000
0<=apples[i]<=10^9
0<=l<=r<n
0<=y<n
The number of apples on a tree never exceeds 10^9.
Sample Input:
10
6 5 12 48 3 20 4 2 3 7
6
COUNT 2 4
COUNT 7 9
GROW 12 4
COUNT 2 4
EAT 6 9
COUNT 7 9
Sample Output:
60
10
63
5
SAMPLE TEST CASE EXPLANATION:
For 'COUNT 2 4', the sum of apples on trees 2,3 and 4 is 12+48+3=63. But as Courage doesn't include the apples on the tree with the minimum number of apples in the specified range (which in this case is the 4th tree), the number that he has to tell Eustace is 12+48=60.
For 'COUNT 7 9', the sum of apples on trees 7,8 and 9 is 2+3+7=12. In this case the tree with the minimum number of apples in the range is the 7th tree. So Courage tell Eustace the number 3+7=10
'GROW 12 4' means that the 4th tree, which has 3 apples, grows 12 more apples on it. So the number of apples on the 4th tree becomes 15.
For 'COUNT 2 4', the answer will be 48+15=63
'EAT 6 9' means that Courage eats 6 apples from the 9th tree. So the 9th tree now has 76=1 apple.
For 'COUNT 7 9, the answer will be 2+3=5.
hide comments
codervrinda:
20170531 14:12:30
Finally AC :)


harshit_walia:
20170210 12:28:36
Easy Peasy:P


hasan356:
20170114 10:04:54
my first segment tree solved in 0.08 

harshgupta007:
20160419 14:17:03
I have used segment trees, still getting tle in Java. Please help 

try2catch:
20160331 14:24:41
Problem statement is not clear about the case when courage tries to eat apples more than available.


rahul2907:
20160121 21:46:24
easy!!! love segment trees always :P 

Prateek Agarwal:
20151213 10:36:37
AC 0.12s in c++ .TLE in Python 

MAYANK NARULA:
20151210 15:26:50
LOVE SEGMENT TREE !! 

saipreethi42:
20151207 11:56:21
Any other surprises to be taken care of? Say, in I/O ? Lots of WA's so far! 

anshal dwivedi:
20150820 05:37:59
AC in one go..! by using STL pair in segment tree..!nice one.:) 
Added by:  Abhinav92003 
Date:  20131005 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 