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 number of employees hired by Trey and Matt. “Q” is the number 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” number 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
erne1309:
2020-12-13 18:34:30
ST get AC in one |
|
jareehd:
2019-10-01 08:25:48
learn new concept
|
|
sapient:
2019-08-26 14:57:37
How can this be solved using binary search ? |
|
aroder:
2019-01-29 16:55:46
simple bit tree implementation... AC in one go!!
|
|
phoemur:
2018-10-12 20:42:45
segTree works fine... |
|
madhur4127:
2018-07-23 06:14:13
@spojabhi, spoj uses 4 bytes of int, and it suffices for this problem, no long long int required. |
|
rajcoolaryan:
2018-06-20 18:05:59
square root decoposition rocks ..
|
|
anirudnits:
2018-06-14 18:54:06
segTree -> TLE
|
|
a_98:
2018-04-25 21:49:04
Good Implementation of Fenwich Trees |
|
draco_malfoy:
2017-12-30 07:55:33
AC in one go :)
|
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 |