白学家 @ 2017-11-25 13:05:45
···
void splay(node * &o,int k) {
o->pushdown();
int d=o->cmp(k);
if (d==1) k-= (o->ch[0]->s )+1;
if (d!=-1) {
node *p=o->ch[d];
p->pushdown();
int d2=p->cmp(k);
int k2=(d2==0?k:k- (p->ch[0]->s) -1);
if (d2!=-1) {
splay(p->ch[d2],k2);
if (d==d2) rotate(o,d^1); else rotate(o->ch[d],d);
}
rotate(o,d^1);
}
}
void splay(node * &o,int k) {
o->pushdown();
int d=o->cmp(k);
if (d==1) k-=o->ch[0]->s+1;
if (d!=-1) {
splay(o->ch[d],k);
rotate(o,d^1);
}
}
by xunzhen @ 2018-01-11 22:07:22
应该一个是单旋,一个是双旋吧
by _WA自动机 @ 2018-02-10 18:06:53
Splay 和 Spaly。。