详解笛卡尔树

· · 题解

为啥要写呢，因为今年CSP考了。不能说完全一样，只能说差不多

其实，笛卡尔树和笛卡尔的关系就如雷峰塔和雷锋的关系一样没有任何关系

什么是笛卡尔树：

  1. 笛卡尔树是一种特殊的二叉树数据结构
  2. 可以用线性的时间完成建树（由此也可以看出，其实平衡树也能线性时间建树）
  3. 笛卡尔树是用栈进行构建的（

大家都应该学过二叉查找树，笛卡尔树也满足二叉查找树的性质：

树中的元素按照中序遍历得到的序列为原数组序列

还记得二叉查找树为什么死了吗？

因为可以通过使用特殊手段将二叉查找树退化成链。

解决办法是可以使用平衡树，但是对于一些题来说太麻烦了。于是我们就可以使用不满足平衡性质的笛卡尔树来解决一些题目。

建树方法：

在栈中存储根节点和右节点。

每次插入新节点时需看是否满足笛卡尔树的性质：

如不满足，则将栈顶的元素弹出，并将其作为新节点的左儿子。

如满足，则把新节点当作栈顶的元素的右儿子，并将其入栈。

总体来说，就是一个模仿单调栈的方法。

代码如下：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        {
            w=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        s=s*10+(ch-'0');
        ch=getchar();
    }
    return w*s; 
}
const int Maxn=1e7+10;
int n,Ar[Maxn];
int siz;

int ch[Maxn][2];

long long ans1,ans2;
long long st[Maxn];

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        //scanf("%d",&Ar[i]);
        Ar[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        int node=0,j;
        while(siz>0 && Ar[st[siz]]>Ar[i])
        {
            j=st[siz--];
            ch[j][1]=node;
            node=j;
        }
        ch[i][0]=node;
        st[++siz]=i;
    }
    int node=0,j;
    while(siz)
    {
        j=st[siz--];
        ch[j][1]=node;
        node=j;
    }
    for(int i=1;i<=n;i++)
    {
        ans1=ans1 xor (long long)(i*(long long)(ch[i][0]+1));
        ans2=ans2 xor (long long)(i*(long long)(ch[i][1]+1));
    }
    printf("%lld %lld",ans1,ans2);
    return 0;
}

温馨提示：

  1. 不开 long long 见祖宗
  2. 不写快读会TLE的

例题：

P1377 （板子）

P4755 （笛卡尔树+CDQ分治）

P3246 （笛卡尔树乱搞）