笛卡尔树构建
柒葉灬
2019-09-18 15:14:25
# 笛卡尔树
-----
笛卡尔树是个二叉树：
满足以下性质：
1. 是一个堆
2. 中序遍历是原序列
-----
构建复杂度：$O(n)$
构建步骤：
1. 维护一个最右边的路径（从根开始一直走右儿子）
2. 插入的时候寻找第一个能成为当前节点父亲的节点
3. (1) 如果有这个节点，那么把它的右儿子作为当前节点的左儿子，当前节点成为它的新右儿子
(2)如果没有，说明当前点是根，那么就把原来的根作为自己的做儿子即可
4. 将当前点塞入栈中
代码：
```cpp
struct node{
int ls,rs,x;
bool operator <(const node &_)const{
return x<_.x;
}
}A[maxn];
for(int i=1;i<=n;i++){
while(top&&A[i]<A[stk[top]])top--;//找一个满足要求的
if(!top)A[i].ls=stk[1];//原来的根
else {
A[i].ls=A[stk[top]].rs;
A[stk[top]].rs=i;
}
stk[++top]=i;
}
```
我并不知道笛卡尔树记录父亲的意义何在，
所以就没有记节点的父亲了。
模板题：noip2018d1t1铺设道路 ， noip2013积木大赛
------