POCA
1 Sec 64 MB | Markdown 显示标签
简单 (*1100) 树状数组
43 | 59 |
通过 | 提交 |
题目描述
Mirko picks up a mysterious bottle that can store numbers. This bottle can store as many numbers as you need.
Why is the bottle so mysterious? Because as long as you give him a number $x$, it can tell you how many numbers are greater than or equal to $x$ in the bottle!
But unfortunately, Mirko accidentally broke the bottle. He wants you to help him write a program to replace the bottle.
---
Mirko 捡到了一个神秘的瓶子,可以存任意多个数字。
为什么说这个瓶子很神秘呢?因为只要你给它一个数字 $x$,它就能告诉你瓶中有多少个数字大于等于 $x$!
但不幸的是,Mirko 不小心打破了这个瓶子。他希望你写个程序来代替这个瓶子的功能。
输入格式
The first line contains a positive integer $q$, representing the number of operations. Each operation may be any of the following three:
- `+ value count1` : put $count1$ numbers $value$ into the bottle;
- `- value count2` : take $count2$ numbers $value$ from the bottle;
- `? value` : print a integer representing how many numbers are greater than or equal to $x$ in the bottle.
It is guaranteed that when the numbers are taken out, there must be a corresponding number of numbers in the bottle before. (No need to worry about illegal situations.)
It is guaranteed that there is at least one operation 3 in the input.
**Assume that the bottle is initially empty.**
$1\le q\le 200000$
$1\le value\le 200000$
$1\le count1\le 10000,\ 1\le count2\le$ Remaining quantity in bottle
输出格式
For each operation 3 above, output a integer representing the answer.
样例输入 #1
7 + 114 514 + 1919 810 ? 314 - 1919 514 + 19198 10 ? 114 ? 11451
样例输出 #1
810 820 10