笛卡尔树

数据结构结构介绍

• 笛卡尔树是一种树形的数据结构，它的每一个节点都有两个值key和weight，其中key满足二叉搜索树的性质，而weight满足堆的性质。在使用时，我们通常将key值排序后放在数组中，方便建树。一个有趣的事实是，如果笛卡尔树的键值确定，且key和weight互不相同， 那么这个笛卡尔树的结构是唯一的。
• 

​ （图片来自oiwiki，其中上面数组中的是weight，数组的下标为key）

唯一性证明

• 我们首先将要处理的数据按照key值从小到大排序，之后对于任意的一段区间，我们知道存在一个相对应的小根堆，而小根堆的堆顶毫无疑问就是整个数组中weight的最小值。最小值将数组分成两个部分，它的左儿子就是它左边区间的最小值，右儿子就是它右边区间的最小值，之后可以递归建出整棵树。因此，这棵树是唯一的。

建树实现

• 将元素按照key排序。然后一个一个插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这个树的右链的末端。于是我们执行这样一个过程，从下往上比较右链结点与当前结点x的weight ，如果找到了一个右链上的结点i满足wi<wx ，就把i接到x的右儿子上，而i原本的右子树就变成x的左子树。以下是我的垃圾实现代码。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN=1e7+7;
ll n,root,a[MAXN];
struct tree_node
{
    ll lkid,rkid,wei,key,fa;
}tree[MAXN];

ll tree_init()
{
    for(ll i=1;i<=n;i++)
    {
        tree[i].key=i;
        tree[i].wei=a[i];
        tree[i].fa=i;
        tree[i].lkid=tree[i].rkid=0;
    }
    ll s[MAXN],top=0,rt=1,p,q;
    s[++top]=1;
    for(ll i=2;i<=n;i++)
    {
        if(tree[rt].wei>tree[i].wei)
        {
            tree[rt].fa=i;
            tree[i].lkid=rt;
            rt=i;
            s[1]=i;
            top=1;
            continue;
        }
        p=1;
        while(p<=top&&tree[s[p]].wei<tree[i].wei)p++;
        if(p>top)
        {
            tree[s[top]].rkid=i;
            tree[i].fa=s[top];
            s[++top]=i;
            continue;
        }
        q=tree[s[p]].fa;
        tree[q].rkid=i;
        tree[i].fa=q;
        tree[s[p]].fa=i;
        tree[i].lkid=s[p];
        top=p;
        s[top]=i;
    }
    return rt;
}

例题

HDU 1506 最大子矩形

洛谷 P5854 【模板】笛卡尔树