on[dir] = f; a->father = f->father; f->father->son[f->Check()] = a; f->father = a; PushUp(f); if(root == f) root = a; } inline void Splay(Complex *a,Complex *aim) { while(a->father != aim) { if(a->father->father == aim) Rotate(a,!a->Check()); else if(!a->father->Check()) { if(!a->Check()) Rotate(a->father,true),Rotate(a,true); else Rotate(a,false),Rotate(a,true); } else { if(a->Check()) Rotate(a->father,false),Rotate(a,false); else Rotate(a,true),Rotate(a,false); } } PushUp(a); } inline void SplaySeg(int l,int r) { l++,r++; Splay(Kth(root,l - 1),nil); Splay(Kth(root,r + 1),root); } Complex *Kth(Complex *a,int k) { PushDown(a); if(a->son[0]->size >= k) return Kth(a->son[0],k); k -= a->son[0]->size; if(k == 1) return a; return Kth(a->son[1],k - 1); }
|