AKVQLD03 - How to Handle the Fans


Trey Parker and Matt Stone, the creators of “South Park” are having some problems handling their fans. The number of fans is so huge that can’t even count them properly. So they hired “N” employees for counting the fans. All the “N” employees had their own separate offices and they were located in a straight line with positions numbered as 1, 2, 3 … up to N. Fans can come to the office of any employee at any time and tell them how they feel about the show and if they are lucky enough, they may get to meet Trey Parker and Matt Stone.

All the employees keep on updating Trey and Matt about the number of fans currently in their offices, so at each moment, they will have a list of “N” positions and the number of fans in each of these positions. Trey and Matt suddenly start taking a walk from office at position “A” to position “B” to meet their fans, but before they start walking they want to know the sum of all the fans in the offices from position “A” to “B”. But counting them one by one is taking a lot of time, so now they hired you, an awesome software engineer to do this task. Your task is to find the sum of all the fans present in the offices between positions “A” to “B” ("A" and "B" inclusive). Let’s see if you could do it fast enough.

Input

The first line of Input contains two integers “N” and “Q”. “N” is the no. of employees hired by Trey and Matt. “Q” is the no. of queries to be followed.

Each of the next “Q” lines contain a query. A query can be of two types:

“add P F” – this means that “F” no. of fans came to the office at Position “P”

“find A B” – this means that Trey and Matt wants to know the sum of fans present at offices at positions “A” to “B”

Output

For each query of the type “find A B”, output the sum of fans present at offices at positions “A” to “B” in a different line.

Constraints

1 <= N <= 10^6

1 <= Q <= 10^5

1 <= A < B <= N

1 <= P <=N

1 <= F <= 10^4

Example

Input:
10 10
find 1 5
add 5 8
add 6 2
find 4 5
find 4 6
add 2 4
find 2 6
add 6 7
find 1 6
find 7 10

Output:
0
8
10
14
21
0

hide comments
jaideeppyne: 2017-09-23 15:02:01

Easy Segment Tree question for beginners !

anubhav1772: 2017-07-21 19:33:56

Yayy!! ac in 1 go :)

Last edit: 2017-07-21 19:34:19
pranav0123: 2017-05-22 21:29:36

Can anyone please find why I am getting runtime error with this segment trees implementation. Submission id: 19459839

krishna_sai: 2017-03-30 07:27:33

spoj says my program has compilation error while its working fine in ideone and codeblocks? Any thing I am overlooking?

vigneshkv: 2016-12-31 11:06:55

simple Binary Indexed Tree .. you can watch the tutorial on youtube.

malibarbar: 2016-08-08 09:32:26

easy segment tree but got wa because next line

xinnix: 2016-07-02 16:06:36

Wow... Easy seg tree.... No need to use bit

atif_11: 2016-05-08 23:29:37

Good implementation of Binary Index Tree...

gautam: 2016-03-10 02:22:28

easy ..ac in one go;)

rahul2907: 2016-01-19 14:24:56

BIT easy one :)


Added by:Ankit Kumar Vats
Date:2013-07-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self