你惯用的 LCT 写法可能有问题
查看原帖
你惯用的 LCT 写法可能有问题
385093
uniqueharry楼主2022/7/3 13:57

复习 LCT\text{LCT} 的时候才发现,这道题的数据有一点弱,如果你 pushdown\text{pushdown} 是这样写的:

void pushdown(int u){
	if(!rev[u]) return;
	swap(ch[u][0], ch[u][1]);
	if(ch[u][0]) rev[ch[u][0]] ^= 1;
	if(ch[u][1]) rev[ch[u][1]] ^= 1;
	rev[u] = 0;
}

而与此同时你的 findroot\text{findroot} 又是这样写的:

int findroot(int x){
	access(x), splay(x);
	while(ch[x][0]) pushdown(x), x = ch[x][0];
	splay(x);
	return x;
}

那就是错的,因为下穿标记之后 xx 的左儿子可能并不存在而陷入死循环,却可以通过本题 。如果不改 pushdown\text{pushdown} 的话,findroot\text{findroot} 正确的写法应为:

int findroot(int x){
	access(x), splay(x);
	for(;;){
	    pushdown(x);
	    if(!ch[x][0]) break;
	    x = ch[x][0];
	}
	splay(x);
	return x;
}
2022/7/3 13:57
加载中...