POJ 3580 SuperMemo(二)
][!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) { Push_Down(r); 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; } int Get_Kth(int r,int k) { Push_Down(r); int t=sz[ch[r][0]]+1; if(k==t) return r; if(t