HDOJ 1890 Robotic Sort - c++编程基础

PGJyPgpOb3RlIHRoYXQgaWYgYSBzYW1wbGUgaXMgYWxyZWFkeSBvbiBpdHMgY29ycmVjdCBwb3NpdGlvbiBQaSAsIHlvdSBzaG91bGQgb3V0cHV0IHRoZSBudW1iZXIgUGkgYW55d2F5LCBpbmRpY2F0aW5nIHRoYXQgdGhlIKGwaW50ZXJ2YWwgYmV0d2VlbiBQaSBhbmQgUGkgobEgKGEgc2luZ2xlIHNhbXBsZSkgc2hvdWxkIGJlIHJldmVyc2VkLiA8YnI+CgoKIAo8YnI+CgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">6 3 4 5 1 6 2 4 3 3 2 1 0
Sample Output

4 6 4 5 6 6
4 2 4 4

Source 2008 “Shun Yu Cup” Zhejiang Collegiate Programming Contest - Warm Up（2）

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn=100100; int root,sz[maxn],ch[maxn][2],pre[maxn],rev[maxn]; int n; void NewNode(int& r,int fa,int k) { r=k; pre[r]=fa; ch[r][0]=ch[r][1]=0; sz[r]=1; rev[r]=0; } void Push_Up(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; } void Upd_Rev(int r) { if(r) { swap(ch[r][0],ch[r][1]); rev[r]^=1; } } void Push_Down(int r) { if(rev[r]) { Upd_Rev(ch[r][0]); Upd_Rev(ch[r][1]); rev[r]=0; } } void Build(int& x,int l,int r,int fa) { if(l>r) return; int mid=(l+r)/2; NewNode(x,fa,mid); Build(ch[x][0],l,mid-1,x); Build(ch[x][1],mid+1,r,x); Push_Up(x); } void Rotate(int x,int kind) { int y=pre[x]; Push_Down(y); Push_Down(x); 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]; pre[y]=x; ch[x][kind]=y; Push_Up(y); } void Splay(int r,int goal) { while(pre[r]!=goal) { if(pre[pre[r]]==goal) { Push_Down(pre[r]); Push_Down(r); Rotate(r,ch[pre[r]][0]==r); } else { Push_Down(pre[pre[r]]); Push_Down(pre[r]); Push_Down(r); int y=pre[r]; int kind=(ch[pre[y]][0]==y); if(ch[y][kind]==r) Rotate(r,!kind); else Rotate(y,kind); Rotate(r,kind); } } Push_Up(r); if(goal==0) root=r; } void init() { root=0; ch[root][1]=ch[root][0]=pre[root]=rev[root]=sz[root]=0; Build(root,1,n,0); } int Get_Max(int r) { Push_Down(r); while(ch[r][1]) { r=ch[r][1]; Push_Down(r); } return r; } void Remove() { Push_Down(root); if(ch[root][0]==0) { root=ch[root][1]; pre[root]=0; } else { int m=Get_Max(ch[root][0]); Splay(m,root); ch[m][1]=ch[root][1]; pre[m]=0; pre[ch[root][1]]=m; root=m; Push_Up(root); } } /************Debug***************/ void showit(int x) { if(x) { Push_Down(x); showit(ch[x][0]); printf("结点: %2d 左儿子: %2d 右儿子: %2d 父结点: %2d size: %2d rev: %2d \n", x,ch[x][0],ch[x][1],pre[x],sz[x],rev[x]); showit(ch[x][1]); } } void Debug() { printf("-------------------------------\n"); printf("root: %d\n",root); showit(root); } /**************BLOCK*****************/ struct BLOCK { int id,num; }block[maxn]; bool cmp(BLOCK a,BLOCK b) { if(a.num!=b.num) return a.num

HDOJ 1890 Robotic Sort(二)