hdu 5071 Chat(模拟|Splay) - c++编程基础

UgaGFzIGV2ZXIgc3Bva2VuIHRvIGF0IGxhc3QsIKGwYWN0aXZlobEgaGVyZSBtZWFucyB0aGUgd2luZG93IGhhcyBub3QgYmVlbiBjbG9zZWQgc28gZmFyLiBUaGUgbG9nZ2luZyBmb3JtYXQgaXMgobBCeWUgdTogY6GxIHdoZXJlIHUgaXMgdGhlIHByaW9yaXR5IGFuZCBjIGlzIHRoZSBudW1iZXIgb2Ygd29yZHMgaGUgaGFzIGV2ZXIgc3Bva2VuIHRvCiB0aGlzIHdpbmRvdy4gSGUgd2lsbCBhbHdheXMgc2F5IGdvb2QgYnllIHRvIHRoZSBjdXJyZW50IHRvcCBnaXJsIGlmIGhlIGhhcyBzcG9rZW4gdG8gaGVyIGJlZm9yZSBoZSBjbG9zZXMgaXQuCiAKPGJyPgpJbnB1dApUaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIFQgKFQgodwgMTApLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHRoZSB0ZXN0IGNhc2VzLjxicj4KPGJyPgpGb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgbigwIDwgbiCh3CA1MDAwKSwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2Ygb3BlcmF0aW9ucy4gVGhlbiBmb2xsb3cgbiBvcGVyYXRpb25zLCBvbmUgaW4gYSBsaW5lLiBBbGwgdGhlIHBhcmFtZXRlcnMgYXJlIHBvc2l0aXZlIGludGVnZXJzIGJlbG93IDEwPHN1cD45PC9zdXA+LgogCjxicj4KT3V0cHV0Ck91dHB1dCBhbGwgdGhlIGxvZ2dpbmcgY29udGVudHMuCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">1 18 Prior Add 1 Chat 1 Add 2 Chat 2 Top 2 Chat 3 Untop Chat 4 Choose 2 Chat 5 Rotate 2 Chat 4 Close 2 Add 3 Prior Chat 2 Close 1
Sample Output

Operation #1: empty.
Operation #2: success.
Operation #3: success.
Operation #4: success.
Operation #5: success.
Operation #6: success.
Operation #7: success.
Operation #8: success.
Operation #9: success.
Operation #10: success.
Operation #11: success.
Operation #12: success.
Operation #13: success.
Operation #14: close 2 with 8.
Operation #15: success.
Operation #16: success.
Operation #17: success.
Operation #18: close 1 with 11.
Bye 3: 2

HintThis problem description does not relate to any real person in THU.

Source 2014 Asia AnShan Regional Contest
Recommend liuyiding | We have carefully selected several similar problems for you: 5081 5080 5079 5078 5077 题意：就是要你写一个聊天窗口管理系统。支持增加窗口。关闭窗口。管理优先级。。。。。详细的还是自己读吧。思路：觉得splay可做就用splay做的。功能也是splay最基本的功能。这题需要注意的是。最后Bye的时候是先给置顶的人然后按队列顺序Bye。详细见代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       using namespace std; typedef long long ll; const int maxn=100100; const int INF=0x3f3f3f3f; //ll sum[maxn<<1];//子结点的和 map
       
         mp; int sz[maxn<<1],pre[maxn<<1],mv[maxn<<1],prr[maxn<<1],ch[maxn<<1][2];//sz记录子树规模,pre记录父结点,val存结点值。ch[k][0],ch[k][1]k的左右儿子。 int val[maxn<<1]; int mi,mo,root,s[maxn<<1];//mi回收内存。mo分配内存。root为根。s为内存池 void Treaval(int x)//Debug部分打出来非常清楚 { if(x) { Treaval(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d \n",x,ch[x][0],ch[x][1],pre[x],sz[x],val[x]); Treaval(ch[x][1]); } } void Debug() { printf("root:%d\n",root); Treaval(root); } void Newnode(int &rt,int v,int pr,int fa) { if(mi)//注意mi记录可用空间大小但里面没有空间所以要先减减。不然会出错 rt=s[--mi]; else rt=mo++; ch[rt][0]=ch[rt][1]=0; //sum[r]=k; pre[rt]=fa; prr[rt]=pr; sz[rt]=1; mv[rt]=rt; val[rt]=v; } void PushUp(int rt) { int ls,rs; if(rt==0) return; ls=ch[rt][0],rs=ch[rt][1]; sz[rt]=sz[ls]+sz[rs]+1; if(prr[mv[ls]]>prr[mv[rs]]) mv[rt]=mv[ls]; else mv[rt]=mv[rs]; if(prr[rt]>prr[mv[rt]]) mv[rt]=rt; //sum[rt]=sum[ls]+sum[rs]+val[rt]; } void Init()//初始化很重要！ { mi=root=0; mo=1; ch[0][0]=ch[0][1]=pre[0]=sz[0]=mv[0]=prr[0]=0; val[0]=0;//建一个虚拟根节点。做标记用。pre==0说明就到根了 Newnode(root,0,0,0);//建真正的根和右儿子。必须加这两个虚拟结点。这样区间操作起来才方便 Newnode(ch[root][1],0,0,root); PushUp(ch[root][1]); PushUp(root); } void Rotate(int x,int w)//旋转。w为旋转方式。0为ZAG(x在右边)。1为ZIG(x在左边)。结点为左子树就右旋。右子树就左旋 { int y=pre[x]; ch[y][!w]=ch[x][w];//把x往上转 pre[ch[x][w]]=y; //PushDown(y) //PushDown(x) if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][w]=y; pre[y]=x; PushUp(y); } void Splay(int rt,int goal)//goal为目标父结点 { int y,w; while(pre[rt]!=goal) { if(pre[pre[rt]]==goal) Rotate(rt,ch[pre[rt]][0]==rt); else { y=pre[rt]; w=(ch[pre[y]][0]==y); if(ch[y][w]==rt) { Rotate(rt,!w); Rotate(rt,w); } else { Rotate(y,w); Rotate(rt,w); } } } PushUp(rt); if(goal==0)//旋转到根时更换根结点 root=rt; } int Get_kth(int rt,int k)//取第k个数的标号 { int tp=sz[ch[rt][0]]+1; if(tp==k) return rt; if(tp>k) return Get_kth(ch[rt][0],k); else return Get_kth(ch[rt][1],k-tp); } int Insert(int pos,int v,int pr)//在pos位置插入一个数

hdu 5071 Chat(模拟|Splay)(四)