更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19525640

大意

这个题要求输出字典序最小的等价的二叉查找树。

思路

首先考虑这个题目，插入键值之后的树，是按照权值与时间来说的，我们将其设为二元组 $(k, t)$，那么我们不难发现这个树是一颗 Treap，权值满足 BST，时间戳满足小根堆。

对于样例，我们可以建出来这样的树：

$(1, 1), (4, 2), (3, 3), (2, 4)$

那么显然 $2$ 和 $4$ 是叶子节点，我们如果要保持这个 Treap 的结构的话，我们如果交换这俩节点的时间戳是没有问题的。

所以对于这种二维结构的维护，那我们可以用笛卡尔树维护，因为笛卡尔树也是一个 Treap，我们按照节点从左到右，时间戳为权值建立笛卡尔树。

那么我们建出来的树，显然是在一个节点有两个子节点的时候，那就是先左再右最优，且父更优。

则我们的有限度为：

$$父节点 \ge 左子节点 \ge 右子节点$$

那不就是一个先序遍历过程嘛。

也就是我们只需要建出一颗笛卡尔树，就直接先序遍历即可。

代码

#include<iostream>
#include<stack>
using namespace std;

const int MAXN = 1e5 + 5;
stack<int> stk;
int l[MAXN], r[MAXN];
int a, n;
int in[MAXN], pos[MAXN];

void dfs(int u){
	cout << u << ' ';
	if(l[u]) dfs(l[u]);
	if(r[u]) dfs(r[u]);
}

int main(){
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> a;
		pos[a] = i;
	}
	stk.push(1);
	for(int i = 2;i <= n;i ++){
		int lst = 0;
		while(!stk.empty() && pos[i] < pos[stk.top()]){
			lst = stk.top();
			stk.pop();
		}
		if(stk.empty()){
			l[i] = lst;
		}
		else{
			l[i] = r[stk.top()];
			r[stk.top()] = i;
		}
		stk.push(i);
	}

	int rt = 0;
	for(int i = 1;i <= n;i ++){
		in[l[i]] ++;
		in[r[i]] ++;
	}

	for(int i = 1;i <= n;i ++){
		if(!in[i]){
			rt = i;
			break;
		}
	}

//	cout << rt << '\n';

//	for(int i = 1;i <= n;i ++){
//		cout << i << ": " << l[i] << ' ' << r[i] << '\n';
//	}

	dfs(rt);

	return 0;
}