链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4736
题意：有最多10000次操作，在一个初始为空的数列中添加或移除元素并保持数列有序，每次操作后，如果数列个数为奇数就输出中间值，如果为偶数就输出中间两个值得平均值。
思路：刚开始写了一发multiset模拟，看吴琦TLE了估计他也是multiset写的，就放弃这个思路了，不过最后证明multiset写的机智一点这题也是能过的。线段树、树状数组都考虑了，最后还是用线段树敲了。虽然数字范围是int内，但是操作最多只有10000次，所以需要离散化。先进行离线，再进行离散化，然后建树进行操作。每个节点维护离散化后新的数组对应的下标值在数列中出现了几次。
查询的时候输入要查询数列第几个数，然后从线段树根节点开始递归判断左右子树的数字个数，如果查询的个数小于等于左子树的数字个数，则在左子树中查询，否则要查询的数字减去左子树数字的个数并在右子树中查询，如此递归直到叶子节点，返回节点值，此时返回的值是离散化数组的下标值，再输出答案就好了。
细节： 1.输出比较恶心，对于double类型不输出后导0，直接用cout是可以的，但是输出量太大可能会TLE，所以我转成字符串输出了。
2.虽然数据都在int范围内，但是相加求平均值时可能会溢出，所以用long long来存，因为这个WA了很久。
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 10100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define MOD 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[MAXN<<2],ans[MAXN],fuck[MAXN],cha[MAXN];
int n,flag;
struct node{
int num;
char op;
int id;
}a[10100];
void pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt){
sum[rt] = 0;
if(l==r) return ;
int m = (l+r)>>1;
build(lson);
build(rson);
}
void update(int c,int x,int l,int r,int rt){
if(l==r){
if(sum[rt]==0&&x==-1){
flag = 1;
return ;
}
sum[rt]+=x;
return ;
}
int m = (l+r)>>1;
if(c<=m) update(c,x,lson);
else update(c,x,rson);
pushup(rt);
}
int query(int c,int l,int r,int rt){
if(l==r){
return l;
}
//cout<<sum[rt<<1]<<" "<<l<<endl;
int m = (l+r)>>1;
int ret;
if(sum[rt<<1]>=c){
ret = query(c,lson);
}
else{
ret = query(c-sum[rt<<1],rson);
}
return ret;
}
void output(double x){
int i;
char ss[200];
sprintf(ss,"%lf",x);
int l = strlen(ss);
for(i=0;i<l;i++){
if(ss[i]=='.') break;
}
if(i==l){
printf("%lf\n",x);
return ;
}
while(ss[l-1]=='0'){
l--;
}
if(ss[l-1]=='.') l--;
for(i=0;i<l;i++){
printf("%c",ss[i]);
}
printf("\n");
}
map<int,int>mp;
int main(){
int i,j,q,t,x;
char str[20];
scanf("%d",&t);
while(t--){
mp.clear();
n = 0;
scanf("%d",&q);
for(i=1;i<=q;i++){
scanf("%s%d",str,&a[i].num);
a[i].op = str[0];
a[i].id = i;
fuck[i] = a[i].num;
}
sort(fuck+1,fuck+1+q);
int p = unique(fuck+1,fuck+1+q)-fuck;
for(i=1;i<p;i++){
ans[i] = fuck[i];
mp[fuck[i]] = i;
}
j = p;
build(1,j,1);
for(i=1;i<=q;i++){
if(a[i].op=='a'){
n++;
update(mp[a[i].num],1,1,j,1);
if(n%2){
printf("%d\n",ans[query(n/2+1,1,j,1)]);
}
else{
ll temp = 0;
temp += ans[query(n/2,1,j,1)];
temp += ans[query(n/2+1,1,j,1)];
double t2 = temp / 2.0;
//printf("%lf\n",t2);
output(t2);
}
}
else{
if(n==0){
puts("Wrong!");
continue;
}
flag = 0;
update(mp[a[i].num],-1,1,j,1);
if(flag==1){
puts("Wrong!");
continue;
}
n--;
if(n==0){
puts("Empty!");
continue;
}
if(n%2){
printf("%d\n",ans[query(n/2+1,1,j,1)]);
}
else{
ll temp = 0;
temp += ans[query(n/2,1,j,1)];
temp += ans[query(n/2+1,1,j,1)];
double t2 = temp / 2.0;
//printf("%lf\n",t2);
output(t2);
}
}
}
}
return 0;
}
/*
10
a 1
a 1000000000
a 1000000000
a -1000000000
a 500
a 60000
r 1000000000
r 1
r 500
a 3000
*/