笛卡尔树建树

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906457

拿个单调队列维护

最后pop出来的就是它的左儿子

现在还在的，它是他的右儿子

1
2
3
4
5
6
7
8
9
10
11
int build() {
	int S[N]; 
	for(int i=1; i<=n; ++i) {
		while(top && T[S[top]].val < T[i].val) 
			T[i].son[0]=S[top], --top; 
		if(top) T[S[top]].son[1]=i; 
		S[++top]=i; 
	}
	top=0; 
	return S[1]; 
}