用的有点少的数据结构

笛卡尔树

前置知识

单调栈

正文

性质

笛卡尔树，是一种不常用的数据结构吧，其同时满足二叉搜索树和小根堆的性质

假设们有一个数组$a_i$，将其数组的下标记为$k$,其权值记为$w$，那么建成的笛卡尔树满足以下性质：

1. $k$值满足二叉搜索树的性质，$ls_k<k<rs_k$
2. $w$值满足小根堆的性质，$ls_w<w,rs_w<w$

建树

首先加入第$i$个数时，$i$肯定在$[1，i-1]$构成的树右链的末尾节点，此时先插入$i$，将其插到右链末尾节点，但此时这颗树不一定满足第二个性质，需要对其进行调整，若此时$i$的父节点的$w$值比$i$大，一直找到右链上$w$值比$i$小的然后，先将$i$节点的左儿子设为这个节点的右儿子，再将这个节点的右儿子设为$i$,将$n$个点插入后，即可得到一棵笛卡尔树。

void build()
{
    int top=0,st[maxn];
    memset(st,0,sizeof(st));
    for(int i=1;i<=n;i++)
    {
        while(top&&a[st[top]]>a[i])top--;
        if(!top)ls[i]=st[top+1];
        else ls[i]=rs[st[top]],rs[st[top]]=i;
        st[++top]=i;
    }
}

问题

我也不知道能干啥 🙃