CDC12_H  Halt The War
The war was terrible, thousands of humans and rainbow people lying down on the streets.
Ronny didn’t know what to do, so he decided to go and search for the Rainbowland Castle
and talk to the King. The rainbowlandians stared at Ronny with caution, waiting him to do
something bad just to get him and rainbowkill him. Finally, Ronny made it to the King’s room
and talked to him about stopping this horrible war. The King accepted Ronny’s proposal, but
only with one condition, Ronny needed to prove once again what humanbeings were capable
of. The King said that if Ronny answered the Q queries that he had for him about an order
line of rainbow people numbered from 1 to N , he and his nation would go away. These rainbow
people had a letter with a number on it (Initially this number it’s 0).
There are two types of queries, modification queries and answer queries. The modification
queries consists on, given an interval from A to B inclusive ([A,B]), Ronny needed to update
those rainbow people’s letter, adding one to the number on it; so, by instance, if the interval is
[1,2], then Ronny needed to add one to the first and second rainbowlandian on the line. The
answer queries consists on, given an interval from A to B inclusive, Ronny should say the sum
of every rainbow people’s letter.
If Ronny can do this, the humans are saved! So he need your help, because he is not really that
good in maths and fast sums.
Input
The first line contains an integer T , which specifies the number of test cases. Then, will follow
the descriptions of T test cases.
For each test case you will get an integer N and an integer Q, that represents the number of
rainbowlandian in the line and the number of queries the King asks for. Then, Q lines will
follow, each containing a string and 2 integers, the type of query, that can be "modification"
or "answer" (Quotes for clarity), the first and the last rainbowlandian that Ronny must have
in mind in order to answer the query.
The input must be read from standard input.
Output
For each input case you must print the string "Scenario #i:" where i is the number of the
test case (Starting by 1), followed by Q lines with the answer of each query. If the query was
a modification query, then you should output "OK" (Quotes for clarity), otherwise, output the
sum of the number from A to B inclusive.
The output must be written to standard output.
INPUT  OUTPUT 
2 4 4 answer 1 4 modification 1 2 modification 2 3 answer 2 2 8 6 modification 2 4 modification 4 8 modification 4 5 answer 8 8 modification 5 7 answer 4 8 
Scenario #1: 0 OK OK 2 Scenario #2: OK OK OK 1 OK 11 
hide comments
naruto09:
20160324 12:24:59
finally AC..great question indeed..C++ users try to avoid the use of cin or cout.. 

Sunil:
20150413 19:20:55
same as horrible 

humble_coder:
20141104 15:24:18
@Tjandra


Rocker3011:
20140704 02:49:51
i knew this was doable with a boosted fenwick tree, such a nice problem to practice!!!!! 

brahim:
20130130 10:24:23
Is A is always less than B? 

Mukund Kumar:
20130103 07:13:34
can anyone please explain the output for answer query??


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130102 22:14:38
phew... It's very hard for me to speed up until faster than 0.97s... finally #1st place (0.9s) after 44 attempts. now I have a new speed trick for "treetype" data structure ;) 
Added by:  Venezuelan Programming League 
Date:  20121027 
Time limit:  0.301s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem used for UCVCEIDEC contest. 