笛卡尔树

通过两个题目更好地理解笛卡尔树

【模板】笛卡尔树

Part 1：定义

定义和Treap相同：（Treap是权值随机的笛卡尔树）

• k满足二叉搜索树性质

• w满足小根堆性质

本题下标为k，元素为w（题目定义）

正常构建的Treap应该是下标为w，元素为k（可以模拟插入过程理解） 例题：树的序 （下面有代码）

Part 2：构建

用单调栈维护插入的位置

（下标已经单调递增了，所以新插入的点只能是已前面点的右儿子、前面点只能是它的左儿子）

• 用单调栈维护一个权值单调递增的下标序列，

• 插入一个点时插入到第一个比它小的点（如果有的话）（作为右儿子）后，如果遇到了比它大的点，将最后一个比它大的点作为左儿子

code

#include<bits/stdc++.h>
#define re register
#define il inline
#define LL long long
using namespace std;
template<typename T>il void read(T &ff){
    T rr=1;ff=0;re char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')rr=-1;ch=getchar();}
    while(isdigit(ch)){ff=(ff<<1)+(ff<<3)+(ch^48);ch=getchar();}
    ff*=rr;
}
const int N=1e7+7;
int n,a[N],stk[N],ls[N],rs[N];
LL L,R;
signed main(){
    read(n);
    for(re int i=1,pos=0,top=0;i<=n;++i){//这是按下标顺序插入元素的代码
        read(a[i]);
        //除了上述的维护左右儿子就是普通单调栈啦
        pos=top;
        while(pos&&a[stk[pos]]>a[i])pos--;
        if(pos)rs[stk[pos]]=i;
        if(pos<top)ls[i]=stk[pos+1];
        stk[top=++pos]=i;
    }
    for(re int i=1;i<=n;++i)L^=1LL*i*(ls[i]+1),R^=1LL*i*(rs[i]+1);
    printf("%lld %lld",L,R);
    return 0;
}

树的序

题意：

给一个生成序列，建出一棵笛卡尔树，求字典序最小的可以得到相同笛卡尔树的生成序列

题解

按题意建好树之后输出先序遍历即可

建树略有不同（代码中有注释）

code

复杂度 O(N)
#include<bits/stdc++.h>
#define re register
#define il inline
#define LL long long
using namespace std;
template<typename T>il void read(T &ff){
    T rr=1;ff=0;re char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')rr=-1;ch=getchar();}
    while(isdigit(ch)){ff=(ff<<1)+(ff<<3)+(ch^48);ch=getchar();}
    ff*=rr;
}
const int N=1e5+7;
int n,a[N],stk[N],ls[N],rs[N];
void dfs(re int x){
    if(x)printf("%d ",x),dfs(ls[x]),dfs(rs[x]);
}
signed main(){
    read(n);
    for(re int i=1,x;i<=n;++i)read(x),a[x]=i;//与笛卡尔树模板不同之处
                                            //这里“把权值当做下标，以下标为权值‘输入’a数组”，就转化成板子啦
    for(re int i=1,pos=0,top=0;i<=n;++i){
        pos=top;
        while(pos&&a[stk[pos]]>a[i])pos--;
        if(pos)rs[stk[pos]]=i;
        if(pos<top)ls[i]=stk[pos+1];
        stk[top=++pos]=i;
    }
    dfs(stk[1]);
    return 0;
}