hdu 5071 Chat(模拟|Splay)(三)
{ Splay(Get_kth(root,pos),0);//因为前面有一个虚拟结点所以实际插的位置为pos+1 Splay(Get_kth(root,pos+1),root); Newnode(ch[ch[root][1]][0],v,pr,ch[root][1]); PushUp(ch[root][1]); PushUp(root); return ch[ch[root][1]][0]; } void Delete(int rt)//删除结点 { Splay(rt,0);//先把该点旋转到根 int pos=sz[ch[rt][0]];//获取它前面有多少个数 Splay(Get_kth(root,pos),0); Splay(Get_kth(root,pos+2),root); s[mi++]=rt; ch[ch[root][1]][0]=0; PushUp(ch[root][1]); PushUp(root); } int main() { int n,op,i,t,pos,rt,top; char cmd[15]; scanf("%d",&t); while(t--) { scanf("%d",&n); Init(); mp.clear(); top=-1; for(i=1;i<=n;i++) { scanf("%s",cmd); if(!strcmp(cmd,"Add")) { scanf("%d",&op); if(mp.count(op)) printf("Operation #%d: same priority.\n",i); else { pos=mp.size(); rt=Insert(pos+1,0,op); mp[op]=rt; printf("Operation #%d: success.\n",i); } } else if(!strcmp(cmd,"Close")) { scanf("%d",&op); if(mp.count(op)) { printf("Operation #%d: close %d with %d.\n",i,op,val[mp[op]]); Delete(mp[op]); if(top==mp[op]) top=-1; mp.erase(op); } else printf("Operation #%d: invalid priority.\n",i); } else if(!strcmp(cmd,"Chat")) { scanf("%d",&op); if(top!=-1) { val[top]+=op; printf("Operation #%d: success.\n",i); } else if(mp.size()) { pos=Get_kth(root,2); val[pos]+=op; printf("Operation #%d: success.\n",i); } else printf("Operation #%d: empty.\n",i); } else if(!strcmp(cmd,"Rotate")) { scanf("%d",&op); if(mp.size()>
=op) { pos=Get_kth(root,op+1); Delete(pos); rt=Insert(1,val[pos],prr[pos]); mp[prr[pos]]=rt; if(pos==top) top=rt; printf("Operation #%d: success.\n",i); } else printf("Operation #%d: out of range.\n",i); } else if(!strcmp(cmd,"Prior")) { if(mp.size()) { pos=mv[root]; Delete(pos); rt=Insert(1,val[pos],prr[pos]); mp[prr[pos]]=rt; if(top==pos) top=rt; printf("Operation #%d: success.\n",i); } else printf("Operation #%d: empty.\n",i); } else if(!strcmp(cmd,"Choose")) { scanf("%d",&op); if(mp.count(op)) { pos=mp[op]; Delete(pos); rt=Insert(1,val[pos],prr[pos]); if(top==pos) top=rt; mp[op]=rt; printf("Operation #%d: success.\n",i); } else printf("Operation #%d: invalid priority.\n",i); } else if(!strcmp(cmd,"Top")) { scanf("%d",&op); if(mp.count(op)) { top=mp[op]; printf("Operation #%d: success.\n",i); } else printf("Operation #%d: invalid priority.\n",i); } else if(!strcmp(cmd,"Untop")) { if(top!=-1) { top=-1; printf("Operation #%d: success.\n",i); } else printf("Operation #%d: no such person.\n",i); } } if(top!=-1) { if(val[top]) printf("Bye %d: %d\n",prr[top],val[top]); Delete(top); } while(sz[root]>2) { pos=Get_kth(root,2); if(val[pos]) printf("Bye %d: %d\n",prr[pos],val[pos]); Delete(pos); } } return 0; }