社区讨论

如果你调了很久还是GG,请注意这个错误

P3690【模板】动态树(LCT)参与者 7已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi7w4o1q
此快照首次捕获于
2025/11/21 04:35
4 个月前
此快照最后确认于
2025/11/21 04:35
4 个月前
查看原帖
注意Rotate里面判断isroot的顺序...
CPP
inline void Rotate(int u)
{
	int v=t[u].fa,w=t[v].fa;
	int b=(t[v].rc==u)?t[u].lc:t[u].rc;
	if(!isroot(v)) (t[w].lc==v?t[w].lc:t[w].rc)=u;
	t[v].fa=u; t[u].fa=w;
	if(b) t[b].fa=v;
	if(t[v].rc==u)	t[u].lc=v,t[v].rc=b;
	else t[u].rc=v,t[v].lc=b;
	pushup(v),pushup(u);
}
如果变成了下面这个
CPP
inline void Rotate(int u)
{
	int v=t[u].fa,w=t[v].fa;
	int b=(t[v].rc==u)?t[u].lc:t[u].rc;
	t[v].fa=u; t[u].fa=w;
   if(!isroot(v)) (t[w].lc==v?t[w].lc:t[w].rc)=u;
	if(b) t[b].fa=v;
	if(t[v].rc==u)	t[u].lc=v,t[v].rc=b;
	else t[u].rc=v,t[v].lc=b;
	pushup(v),pushup(u);
}
就GG了 调了好几天的惨痛教训

回复

8 条回复,欢迎继续交流。

正在加载回复...