ZOJ 3612 Median (multiset)

Median

Time Limit: 5 Seconds      Memory Limit: 65536 KB

The median of m numbers is after sorting them in order, the middle one number of them if m is even or the average number of the middle 2 numbers if m is odd.

You have an empty number list at first. Then you can add or remove some number from the list.

For each add or remove operation, output the median of the number in the list please.

This problem has several test cases. The first line of the input is an integer T (0<T<=100) indicates the number of test cases. The first line of each test case is an

integer n(0<n<=10000) indicates the number of operations. Each of the next n lines is either "add x" or "remove x"(-231<=x<231) indicates the operation.

For each operation of one test case: If the operation is add output the median after adding x in a single line. If the operation is remove and the number x is

not in the list, output "Wrong!" in a single line. If the operation is remove and the number x is in the list, output the median after deleting x in a single line, however the list is empty output "Empty!".

if the result is an integer DO NOT output decimal point. And if the result is a double number , DO NOT output trailing 0s.

题意：给你一个容器，每次执行add或者remove操作，当容器不为空时，输出容器中元素的中位数；如果为空，输出Empty！或者Wrong！

分析：比赛时也想到了用multiset，但是删除时会把所有相同的元素一起删掉，没想到用指针指向要删除的元素。这题还可以用树状数组或者线段树来做。