关于 LCT
  • 板块学术版
  • 楼主_5011_
  • 当前回复10
  • 已保存回复10
  • 发布时间2020/5/18 20:29
  • 上次更新2023/11/7 02:12:10
查看原帖
关于 LCT
91127
_5011_楼主2020/5/18 20:29

如果我的 splay 写法比较诡异,不维护父亲,怎么写 lct 啊 /kel

拒绝玩某 lct 维护 splay 的梗。

splay 写法:

void Splay_(Node *&p, int rk) {
	PushDown(p);
	if (rk == GetSize(p->l)) {
		return;
	}
	if (rk < GetSize(p->l)) {
		PushDown(p->l);
		if (rk == GetSize(p->l->l)) {
			RotateR(p);
			return;
		} else if (rk < GetSize(p->l->l)) {
			Splay_(p->l->l, rk);
			RotateR(p);
			RotateR(p);
		} else {
			rk -= GetSize(p->l->l) + 1;
			Splay_(p->l->r, rk);
			RotateL(p->l);
			RotateR(p);
		}
	} else {
		PushDown(p->r);
		rk -= GetSize(p->l) + 1;
		if (rk == GetSize(p->r->l)) {
			RotateL(p);
			return;
		} else if (rk < GetSize(p->r->l)) {
			Splay_(p->r->l, rk);
			RotateR(p->r);
			RotateL(p);
		} else {
			rk -= GetSize(p->r->l) + 1;
			Splay_(p->r->r, rk);
			RotateL(p);
			RotateL(p);
		}
	}
}
2020/5/18 20:29
加载中...