70287 - CSP-S第一轮同测模拟卷1-完善程序1
统计题目(材料题)
（1）单调栈与笛卡尔树：给定一个长度为 n 的数组 a，构建其笛卡尔树（Cartesian Tree）。
01 #include <iostream>
02 #include <stack>
03 using namespace std;
04
05 const int MAXN = 100005;
06 int n;
07 int a[MAXN];
08 int lc[MAXN], rc[MAXN]; // 左右孩子
09 int parent[MAXN];
10 int root;
11
12 void build() {
13 stack<int> st;
14 for (int i = 1; i <= n; ++i) {
15 int last = 0;
16 while (!st.empty() && ①) {
17 last = st.top();
18 st.pop();
19 }
20 if (!st.empty()) {
21 ②;
22 rc[st.top()] = i;
23 }
24 if (last != 0) {
25 ③;
26 }
27 ④;
28 }
29 ⑤;
30 }
31
32 int main() {
33 cin >> n;
34 for (int i = 1; i <= n; ++i) cin >> a[i];
35 build();
36 cout << root << endl;
37 return 0;
38 }
关注我们
