笛卡尔树模板

Posted on | In

参考：笛卡尔树学习笔记 - 作业部落 Cmd Markdown 编辑阅读器

笛卡尔树是一种二叉树，每个节点维护两个值，一个是需要满足二叉搜索树性质的val，另一个是需要满足堆性质的priority。

在val排好序的情况下，笛卡尔树可以在线性时间内构建。一个有用的结论是，对于一组固定的节点，构造出的笛卡尔树是唯一的。

例如下图中，数组下标是val，元素值是priority

image

构建方法很简单，先将节点按照val排序，然后挨个从右边插入（这就是为什么代码中r[0]的值也是rt），同时用单调栈维护右链（递增或递减），然后插入节点时弹出的链变为节点的左子树，再将节点连在右链下。

http://poj.org/problem?id=1785

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<assert.h>
using namespace std;

const int maxn=5e4+2;

struct node{
    string label;
    int pri;
    friend bool operator<(node x,node y){
        return x.label<y.label;
    }
}ns[maxn];

int n,l[maxn],r[maxn],stk[maxn],p,rt;

void build(){
    for(int i=1;i<=n;i++){
        while(p&&ns[i].pri>ns[stk[p]].pri){
            l[i]=stk[p--];
        }
        r[stk[p]]=i;
        stk[++p]=i;
    }
    assert(r[0]==stk[1]);
    rt=stk[1];
}

void output(int o){
    putchar('(');
    if(l[o]){
        output(l[o]);
    }
    cout<<ns[o].label<<'/'<<ns[o].pri;
    if(r[o]){
        output(r[o]);
    }
    putchar(')');
}
int main(){
    while(cin>>n&&n){
        p=0;
        memset(l,0,sizeof(int)*(n+1));
        memset(r,0,sizeof(int)*(n+1));
        string label;
        int pri;
        for(int i=1;i<=n;i++){
            getchar();
            getline(cin,label,'/');
            cin>>pri;
            ns[i].label=label;
            ns[i].pri=pri;
        }
        sort(ns+1,ns+1+n);
        build();
        output(rt);
        cout<<endl;
    }
}

拓展

再看一道难一点的题https://codeforces.com/contest/1220/problem/F

官方做法是用线段树，维护每次移动后每个节点的祖先数目。然后最多的祖先数目就是树深。现在考虑怎么用笛卡尔树来做。

看博客补充了一个笛卡尔树的黑科技：在插入节点时不断维护树的高度。原理很清晰，我们维护右链上每个节点的子树的深度，在插入节点时看它冲掉了哪些右链节点，在这些节点里面取最深的+1，就是新节点子树的深度；如果一个都没有冲掉，那么该节点的位置（链长）就是它的子树深度。注意这里子树深度说的是，这个子树里最深的点在整棵树中的深度。这样一来，我们就可以维护全局最小点两侧不断插入节点后的树深。整棵树的深度就是两侧较大的再+1。枚举全局最小点应该在哪个位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+2;
int n,a[maxn],val[maxn];
int ls[maxn],rs[maxn],stk[maxn],p,rt;
int dpl[maxn],dpr[maxn];

//dp记录添加某个点后子树深度，这个可以通过笛卡尔树建树搞出来，l和r分别表示在全局最小元素的左边和右边

int tmp_dep[maxn];  //表示栈中第i个元素的子树所能达到的深度
void solve_dp(int* dp){
    p=0;
    int mx=0;           //当前树高
    for(int i=1;i<n;i++){
        int tmp=0;    //当前节点能冲掉的栈中节点的子树深度，如果一个都冲不掉，那么该节点的子树深度就是它本身，即链长
        while(p&&val[i]<val[stk[p]]){
            tmp=max(tmp,tmp_dep[stk[p--]]);
        }
        stk[++p]=i;
        if(tmp==0){
            tmp_dep[i]=p;
        }else{
            tmp_dep[i]=tmp+1;   //能冲掉的最深的节点的子树深度 加上它本身
        }
        dp[i]=(mx=max(mx,tmp_dep[i]));
    }
}

int main(){
    cin>>n;
    int mn=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<a[mn]){
            mn=i;
        }
    }
    for(int i=1,j=(mn-2+n)%n+1;i<n;i++,j=(j-2+n)%n+1){
        val[i]=a[j];
    }
    solve_dp(dpl);
    for(int i=1,j=mn%n+1;i<n;i++,j=j%n+1){
        val[i]=a[j];
    }
    solve_dp(dpr);
    int res=1,ans=2e9;
    for(int i=1;i<=n;i++){
        if(max(dpl[i-1],dpr[n-i])+1<ans){
            res=i;
            ans=max(dpl[i-1],dpr[n-i])+1;
        }
    }
    cout<<ans<<' '<<(mn+n-res)%n<<endl;
}