1 // File Name: 4736.cpp  2 // Author: darkdream  3 // Created Time: 2014年07月23日 星期三 11时48分03秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long  25 using namespace std; 26 int ok = 1; 27 const int inf = ~0U>>1; 28 class treap{ 29     struct node{ 30         int value,key,size,num; 31         node(int v , node *n):value(v) 32         {c[0] = c[1] = n; size = 1;num = 1; key = rand()-1;} 33         void rz(){size = c[0]->size + c[1]->size+ num;} 34         node *c[2]; 35     }*root,*null; 36     void rot(node *&t ,bool d) 37     { 38         node *c  =  t->c[d]; 39         t->c[d] = c->c[!d]; 40         c->c[!d] = t;  41         t->rz(); 42         c->rz(); 43         t = c; 44     } 45     void insert(node *&t ,int x) 46     { 47         if(t == null) 48         { 49             t= new node(x,null); 50             return ;  51         } 52         if(x == t->value){ 53             t->num++;  54             t->rz(); 55             return ; 56         }  57         bool d = x > t->value; 58         insert(t->c[d],x); 59         if(t->c[d]->key < t->key) 60             rot(t,d); 61         else t->rz(); 62     } 63     void Delete(node *&t,int x) 64     { 65         if(t == null) 66         { 67           ok = 0;  68           return ; 69         } 70     //    printf("%d %d %d\n",x,t->value,t->num); 71         if(t->value =http://www.mamicode.com/= x && t-> num != 1) 72         { 73             t->num -- ; 74             t->rz(); 75             return ;  76         } 77         if(t->value =http://www.mamicode.com/=  x) 78         { 79             bool  d= t->c[1]->key  < t->c[0]->key; 80             if(t->c[d] == null) 81             { 82                 delete t;  83                 t = null; 84                 return ; 85             } 86             rot(t,d); 87             Delete(t->c[!d],x); 88         }else { 89             bool d = x > t->value; 90             Delete(t->c[d],x); 91         } 92         t->rz(); //相当于pushup 93     } 94     void F(node *t) 95     { 96        if(t == null) 97            return; 98        if(t->c[1] != null) 99            F(t->c[1]);100        if(t->c[0] != null)101            F(t->c[0]);102        delete t;103        t = null;104     }105     int select(node *t ,int k)106     {107         int r = t->c[0]->size;108         int l = t->c[0]->size + t->num;109         if(k > r && k <= l)110         {111             return t->value;112         }113         if(k <= r)  return select(t->c[0],k);114         return select(t->c[1],k-l);115     }116     public:117     treap()118     {119         null = new node(0,0);120         null->size = 0 ; 121         null->num = 0 ; 122         null->key = inf;123         root = null;124     }125     void ins(int x)126     {127         insert(root ,x);128     }129     void del(int x)130     {131         Delete(root,x);132     }133     void count()134     {135         //printf("%d\n",k);136         if(root == null ){137             printf("Empty!\n");138             return ;139         }140         int k = root->size;141         if(k % 2 == 1)142         {143             printf("%d\n",select(root,k/2+1));144         }else{145             LL temp = 1ll*select(root,k/2) + select(root,k/2+1);146             if(temp % 2 == 0 )147                 printf("%lld\n",temp/2);148             else printf("%.1f\n",temp*1.0/2);149         }150     }151     void free()152     {153        F(root);154     }155 156 };157 int main(){158     //freopen("in.txt","r",stdin);159     //freopen("output.txt","w",stdout);160     int ca; 161     scanf("%d",&ca);162     while(ca --)163     {164         int n ;165         scanf("%d",&n);166         treap T;167         for(int i =1 ;i <= n;i ++)168         {169             char str[10];170             int x;171             scanf("%s %d",str,&x);172             if(str[0] == ‘r‘)173             {174                 ok =1 ; 175                 T.del(x);176                 if(ok == 0 )177                 {178                     printf("Wrong!\n");179                 }else{180                     T.count();181                 }182             }else{183                 T.ins(x);184                 T.count();185             }186         }187         T.free();188     }189     return 0;190 }