题面：[TJOI2011] 树的序
题目描述
众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：
- 空树中加入一个键值 $k$，则变为只有一个结点的二叉查找树，此结点的键值即为 $k$。
- 在非空树中插入一个键值 $k$，若 $k$ 小于其根的键值，则在其左子树中插入 $k$，否则在其右子树中插入 $k$。
我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为 $n$ 的生成序列，先比较第一个插入键值，再比较第二个，依此类推。
输入格式
第一行，一个整数 $n$，表示二叉查找树的结点个数。第二行，有 $n$ 个正整数 $k_1, k_2, \cdots,k_n$，表示生成序列，简单起见，$k_1 \sim k_n$ 为一个 $1$ 到 $n$ 的排列。
输出格式
一行，$n$ 个正整数，为能够生成同样二叉查找树的所有生成序列中最小的。
样例 #1
样例输入 #1
样例输出 #1
提示
数据范围及约定
- 对于 $20\%$ 的数据， $1\le n ≤ 10$。
- 对于 $50\%$ 的数据， $1\le n ≤ 100$。
- 对于 $100\%$ 的数据， $1\le n ≤ 10^5$。
思路
首先，要我们构造一个一模一样的二叉搜索树，那么就说明，我们要建的树，他要满足这个二叉搜索树的要求；第二，他是按照插入顺序来的，说明他其实还是个以下标为键值的小根堆。
然后就直接以 a[i] 为第一键值，下标为第二键值，建立笛卡尔树即可。显然答案是这个笛卡尔树的前序遍历
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 1e5 + 10;
int n;
pair<int , int > a[N];
inline void Input() {
read(n);
for(int i = 1; i <= n; i++) {
read(a[i].first);
a[i].second = i;
}
}
int stk[N], top;
int ls[N], rs[N], rt;
void Dfs(int u) {
if(u == 0) return ;
printf("%d ", u);
Dfs(ls[u]);
Dfs(rs[u]);
}
inline void Work() {
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) {
int k = top;
while(k > 0 && a[i].second < a[stk[k]].second) k--;
if(k) rs[stk[k]] = i;
else rt = i;
if(k < top) ls[i] = stk[k + 1];
stk[++k] = i;
top = k;
}
Dfs(rt);
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
