| Beads |
| Time Limit: 1000ms, Special Time Limit:2500ms,Memory Limit:65366KB |
| Problem description |
| A game consists of putting beads in boxes. The rules of the game are too complex to describe here, but all you need to know is that keeping track of the number of beans in adjacent boxes are very important to the outcome of the game. You are asked by a friend to write a program to help him win the game every time. At the start of a game, all boxes are empty. |
| Input |
| The first line of the input consists of a single number T, the number of games played. Each game start with a line describing B, P and Q, the number of boxes, put requests and query requests, respectively. Then follows P + Q lines with either P i a, saying a beads are put in box number i,or Q i j, a query request for the number of beads in boxes i through j, inclusive. |
| Output |
| For each query request, output the number of beads in boxes a through b, inclusive, that are in the boxes at this point of the game. |
| Sample Input |
1 7 5 3 P 2 1 P 3 3 P 4 7 Q 1 4 P 7 6 Q 4 4 P 6 4 Q 1 7 |
| Sample Output |
11 7 21 |
| Judge Tips |
| 0 < T 100 0 < B 100000 0 < P 30000 0 < Q <= 30000 0 <= a <= 100 0 < i <= j <= B Note that boxes are 1-indexed. This is an I/O-heavy problem. For Java programmers, this means that you should use BufferedReader for input reading (not Scanner). It is also bene cial to build all output in a StringBuilder before printing in a single print statement. |
| Problem Source |
|
IDIOPEN 2011
題目大意：赤裸裸的樹狀數組模板啊，但是不會碼，只好碼線段樹了，第一次碼線段樹，糾結~~囧。。調試了1個小時，囧。。 思路：cover：表示的是如果插入的數在某個區間內，該區間的cover就要相應加上該值。我無限調試在mid用的是線段的那一種情況，所以在分左右子樹的時候沒有mid+1.囧。。。
program： #include<iostream> |