非旋Treap建树的问题

非旋treap笛卡尔式建树的时候我发现了一些我不能解决的问题，请大佬们帮忙看看。

CPP

int Build(int c[], int num) {
	static int S[kMaxn]; // 栈，维护最右链
	int top = 0;
	for (int i = 0, cur, last; i < num; i++) {	
		cur = NewNode(c[i]), last = 0; // NewNode新建一个节点，并返回定义数组下标
        for (int fa; top; ) {
        //	rkey是随机权值，维护的是小根堆
			if (T[S[top - 1]].rkey < T[cur].rkey) {
				lson(cur) = rson(fa = S[top - 1]); Maintain(cur);
				rson(fa) = cur; Maintain(fa);
				break;
			}
			last = S[--top];
		}
        // 这里特判把栈弹空的情况
		if (!top && last) {
			lson(cur) = last; Maintain(cur);
		}
		S[top++] = cur;
	}
	return S[0];
}

这是我原来的代码，除了Build函数其他函数都可以保证没有问题（暴力建树是没有WA的），Maintain函数用于维护这个节点的信息（即把儿子的信息pushup上去）。在这里建树的时候每次son的信息发生改变我就Maintain一次，但是这样只能通过第一个点，其他点全部WA。

下面是AC的代码：

CPP

int Build(int c[], int num) {
	static int S[kMaxn];
	int top = 0;
	for (int i = 0, cur, last; i < num; i++) {	
		cur = NewNode(c[i]), last = 0;
		for (int fa; top; ) {
			if (T[S[top - 1]].rkey < T[cur].rkey) {
				lson(cur) = rson(fa = S[top - 1]); rson(fa) = cur;
				break;
			}
			Maintain(last = S[--top]);
		}
		if (!top && last) {
			lson(cur) = last;
		}
		S[top++] = cur;
	}
	while (top) Maintain(S[--top]);
	assert(S[0]); // 这个assert后来并没有报错
	return S[0];
}

它与原来代码的唯一区别就是它是在一个点出栈的时候进行Maintain。但是我认为这两种方法无非就是第一种进行Maintain操作次数多一些。至于为什么导致WA，我实在是看不出，请大佬们帮助我一下。感激不尽。

非旋Treap建树的问题

讨论操作

回复

相关推荐

非旋Treap建树的问题