笛卡尔树
笛卡尔树和笛卡尔的关系就像雷峰塔和雷锋一样，一点关系也没有（
笛卡尔树的概念
笛卡尔树本质是一种固定结构的二叉搜索树，同时具有堆的性质。
笛卡尔树是一种二叉树，每一个节点由一个键值二元组 $ (k,w) $ 构成．要求 \(k\) 满足二叉搜索树（BST）的性质，而 \(w\) 满足堆的性质．如果笛卡尔树的 \(k,w\) 键值确定，且 \(k\) 互不相同，\(w\) 也互不相同，那么这棵笛卡尔树的结构是唯一的。
以上是 OI Wiki 中对于笛卡尔树的定义，其实笛卡尔树就是二叉搜索树的固定形式，treap等数据结构也可以视为笛卡尔树。
平时使用时，通常将下标 \(i\) ，作为键值 \(k\) ，将元素值作为 \(w\)。
依据笛卡尔树升序降序要求的不同，也可以将笛卡尔树分为大根笛卡尔树和小根笛卡尔树。
下图即为一颗满足小根堆性质的笛卡尔树。
笛卡尔树的建树
通常使用单调栈构建笛卡尔树，时间复杂度为\(O(n)\)。
以下构建过程会建出一颗满足小根堆性质的笛卡尔树，想要构建满足大根堆性质的笛卡尔树同理。
考虑从左至右构建笛卡尔树的过程中，每次加入一个元素，它只会加入到右链中（前面的所有元素均处于它的左边），那么所有节点的左链一定都是不变的，所以只需要动态维护右链。
用单调栈维护右链，则每次新加入一个节点，就不断弹栈，知道第一个小于当前元素键值\(w\)，就将新加入的元素设为该节点的右儿子，将最后一个弹出栈的元素设为当前元素的左儿子。
对于每个至多只会入栈，出栈各一次，时间复杂度\(O(n)\)。
该方法也可以拓展至构建平衡树，即\(O(n)\)建出一颗平衡树。
此方法可用于当插入操作很少，\(O(n \log n)\)建树会成为瓶颈时，或者一次插入大量连续的元素时，可以先建出平衡树，再合并。
笛卡尔树相关例题
P5854 【模板】笛卡尔树
link.
单调栈建笛卡尔树板子题。
Code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 2e9
#define eps 1e-9
#define ls 2*k
#define rs 2*k+1
using namespace std;const int N = 1e7 + 5,M = 1e6 + 5;
const int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};int n,rt,p[N],son[N][2];
inline int build(){stack<int> stk;p[0] = -inf , stk.push(0);for(int i = 1;i <= n;i++){int lst = 0;while(!stk.empty() && p[stk.top()] > p[i])lst = stk.top() , stk.pop();son[stk.top()][1] = i , son[i][0] = lst , stk.push(i);}return son[0][1];
}
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int tc = 1;while(tc--){cin >> n;for(int i = 1;i <= n;i++) cin >> p[i];rt = build();int ans1 = 0,ans2 = 0;for(int i = 1;i <= n;i++){ans1 = ans1 ^ (i * (son[i][0] + 1));ans2 = ans2 ^ (i * (son[i][1] + 1));}cout << ans1 << " " << ans2 << "\n";}return 0;
}
P1377 [TJOI2011] 树的序
link.
理解一下题面，问题本质是以 \(k_i\) 为键值 \(k\) （满足BST的性质），以 \(i\) 为键值 \(w\) （满足小根堆的性质），那么可以根据给出的生成序列建出笛卡尔树。
树的形态不能改变，那么父亲节点一定要先于子节点，同时要让新字典序最小，那么先分配给左子树是优于先分配右子树的，也就是在笛卡尔树上前序遍历（Root - L - R）。
时间复杂度：\(O(n)\)。
Code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 2e9
#define eps 1e-9
#define ls 2*k
#define rs 2*k+1
using namespace std;const int N = 1e5 + 5,M = 1e6 + 5;
const int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};int n,rt,p[N],son[N][2];
inline int build(){stack<int> stk;p[0] = -inf , stk.push(0);for(int i = 1;i <= n;i++){int lst = 0;while(!stk.empty() && p[stk.top()] > p[i])lst = stk.top() , stk.pop();son[stk.top()][1] = i , son[i][0] = lst , stk.push(i);}return son[0][1];
}
void dfs(int x){cout << x << " ";if(son[x][0]) dfs(son[x][0]);if(son[x][1]) dfs(son[x][1]);return ;
}
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int tc = 1;while(tc--){cin >> n;for(int i = 1,x;i <= n;i++) cin >> x , p[x] = i;rt = build() , dfs(rt);}return 0;
}
P2171 Hz 吐泡泡
link.
这道题目与P1377 [TJOI2011] 树的序很相似。
考虑 \(a_i\) 满足键值 \(k\) (BST) ， \(i\) 满足键值 \(w\)（堆）。
所以将原序列按 \(a_i\) 排序后，用单调栈构建笛卡尔树。
最后后序遍历输出即可。
时间复杂度：\(O(n)\)。
Code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 2e9
#define eps 1e-9
#define ls 2*k
#define rs 2*k+1
using namespace std;const int N = 3e5 + 5,M = 1e6 + 5;
const int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};int n,rt,son[N][2];
int ans[N],dep[N],top,deep;
struct node{int x,id;friend bool operator < (node x,node y){ return x.x < y.x; }
}p[N];
inline int build(){stack<int> stk;p[0].id = -inf , p[0].x = 0 , stk.push(0);for(int i = 1;i <= n;i++){int lst = 0;while(!stk.empty() && p[stk.top()].id > p[i].id)lst = stk.top() , stk.pop();son[stk.top()][1] = i , son[i][0] = lst , stk.push(i);}return son[0][1];
}
void dfs(int x){if(son[x][0]) dep[son[x][0]] = dep[x] + 1 , dfs(son[x][0]);if(son[x][1]) dep[son[x][1]] = dep[x] + 1 , dfs(son[x][1]);ans[++top] = x , deep = max(deep , dep[x]);return ;
}
signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int tc = 1;while(tc--){cin >> n;for(int i = 1,x;i <= n;i++) cin >> p[i].x , p[i].id = i;sort(p + 1,p + n + 1);rt = build() , dep[rt] = 1 , dfs(rt);cout << "deep=" << deep << "\n";for(int i = 1;i <= n;i++) cout << p[ans[i]].x << "\n";}return 0;
}