题目大意:
添加和删除一个数,然后输出中位数。
简单的Splay 维护Splay上有多少个节点就可以了
#include <cstdio> #include <iostream> #define inf 1LL<<60 #define maxn 222222 #define keyTree (ch[ch[root][1]][0]) using namespace std; typedef long long LL; int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn]; int root,top1,top2; LL val[maxn]; void New(int &x,int PRE,LL v) { if(top2)x=S[--top2]; else x=++top1; ch[x][0]=ch[x][1]=0; siz[x]=1; pre[x]=PRE; /*special*/ val[x]=v; } void pushup(int x)/*special*/ { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; } void pushdown(int x) { } void Rotate(int x,int kind) { int y=pre[x]; pushdown(x); pushdown(y); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; pushup(y); } void Splay(int x,int goal) { pushdown(x); while(pre[x]!=goal) { if(pre[pre[x]]==goal) Rotate(x,ch[pre[x]][0]==x); else { int y=pre[x]; int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x){ Rotate(x,!kind); Rotate(x,kind); } else { Rotate(y,kind); Rotate(x,kind); } } } pushup(x); if(goal==0)root=x; } //把左数第k号节点放在goal下面 //调用了splay void RotateTo(int k,int goal) { int r=root; pushdown(r); while(siz[ch[r][0]]!=k) { if(k<siz[ch[r][0]]) { r=ch[r][0]; } else { k-=siz[ch[r][0]]+1; r=ch[r][1]; } pushdown(r); } Splay(r,goal); } //删除节点x 并回收内存 void erase(int x) { int y=pre[x]; int head=0,tail=0; for(que[tail++]=x;head<tail;head++) { S[top2++]=que[head]; if(ch[que[head]][0])que[tail++]=ch[que[head]][0]; if(ch[que[head]][1])que[tail++]=ch[que[head]][1]; } ch[y][ch[y][1]==x]=0; pushup(y); } //插入节点 键值为k void init()/*special*/ { root=top1=top2=0; ch[0][0]=ch[0][1]=siz[0]=pre[0]=0; New(root,0,-inf); New(ch[root][1],root,inf); siz[root]=2; } int tot; void insert(LL x,int pos) { if(x<=val[pos]) { if(ch[pos][0]==0) { Splay(pos,0); int l=siz[ch[root][0]]; RotateTo(l-1,0); RotateTo(l,root); New(keyTree,ch[root][1],x); } else insert(x,ch[pos][0]); } else { if(ch[pos][1]==0) { Splay(pos,0); int l=siz[ch[root][0]]; RotateTo(l,0); RotateTo(l+1,root); New(keyTree,ch[root][1],x); } else insert(x,ch[pos][1]); } } void print() { if(tot&1) { RotateTo(tot/2+1,0); printf("%lld\n",val[root]); } else { RotateTo(tot/2,0); LL l=val[root]; RotateTo(tot/2+1,0); LL r=val[root]; if((l+r)%2)printf("%.1lf\n",(l+r)/2.0); else printf("%lld\n",(l+r)/2); } } bool remove(LL x,int pos) { if(pos==0) { printf("Wrong!\n"); return false; } if(x==val[pos]) { Splay(pos,0); int l=siz[ch[root][0]]; RotateTo(l-1,0); RotateTo(l+1,root); keyTree=0; return true; } else if(x<val[pos]) { return remove(x,ch[pos][0]); } else return remove(x,ch[pos][1]); return true; } int main() { int T; scanf("%d",&T); while(T--) { init(); tot=0; int m; scanf("%d",&m); while(m--) { char str[20]; LL op; scanf("%s%lld",str,&op); if(str[0]==‘a‘) { insert(op,root); tot++; print(); } else { if(remove(op,root)) { tot--; if(tot)print(); else printf("Empty!\n"); } } } } return 0; }
zoj 3612 Median (splay),布布扣,bubuko.com
原文:http://blog.csdn.net/u010709592/article/details/25074317