笛卡尔树算法总结

 

如果你学了平衡树，应该会觉得笛卡尔树很简单。

笛卡尔树

笛卡尔树是一种二叉搜索树，但是他的权值和优先级是被给定了的。因为优先级被给定，所以笛卡尔树的形态只能有 种。

可以发现笛卡尔树的点的相对位置和在数组中的相对位置是对应上了的。

于是我们考虑如何建出来这一棵笛卡尔树。

有一种 的做法。首先从左往右扫，因为是笛卡尔树，每个位置和数组有对应关系，所以新增的节点 一定在这棵笛卡尔树的右链上（就比如上面这个图的 24-19 这条链）。

因为优先级是从浅到深递减的，我们可以从右链的底端开始往上扫，如果扫到的这个点 的优先级比新增的节点 的优先级小，那么就继续往上扫。否则说明 优先级比 大，就在这里停住。

为了满足位置关系，我们只能把新增的这个点在中序遍历中是最后面的。所以我们把原来的 的右儿子给接到 的左儿子（因为后面还有点，所以要预留 的右儿子）。把 接到原来 的右儿子。这样就维持了这棵笛卡尔树的形态。

我们可以借助栈这个结构来维护这个关系。我们设这个栈就是这棵笛卡尔树的右链，每加入一个节点就先检查这个栈里面第一个比 优先级大的点，比 优先级小的点就用 while 扫把它给 pop 出栈外（因为这些都是要被加入左儿子的点，以后用不到了）。然后就修改儿子和父亲的关系。修改完了之后就把该点加入右链里面。由于每个节点都会入栈，有些节点会出栈有些节点不会出栈，那么我们就得到了一个 的做法！

int st[N], len; //手写栈
void build(){
    for(int i=1;i<=n;i++){
        int pos = st[len]; // 取右链的最后一个节点
        while(len && tr[pos].pri < tr[i].pri){ // 当右链有节点并且最后一个节点的优先级比新增节点的优先级小
            pos = tr[pos].fa; // 就跳到他的父亲。因为父亲的优先级一定比扫到的这个点的优先级大
            len--; // 栈 pop 操作，把这个点 pop 出栈外
        }
        tr[i].ls = tr[pos].rs; // 把第一个比 i 优先级大的点 pos 的右儿子插入到 i 的左儿子下
        tr[tr[pos].rs].fa = i; // 对应的，设置 i 的新左儿子的父亲
        tr[pos].rs = i; // 设置 pos 的右儿子为 i
        tr[i].fa = pos; // 对应的，设置 i 的父亲为 pos
        st[++len] = i; // 将节点插入栈
    }
}

以数小优先级大的笛卡尔树为例的图解（图源OI-WIKI）：

P5854 模板笛卡尔树

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+6;
typedef long long ll;
struct node{
    int ls, rs, pri, val, fa;
}tr[N];
int n;
int st[N], len;
void build(){
    for(int i=1;i<=n;i++){
        int pos = st[len];
        while(len && tr[pos].pri < tr[i].pri){
            pos = tr[pos].fa;
            len--;
        }
        tr[i].ls = tr[pos].rs;
        tr[tr[pos].rs].fa = i;
        tr[pos].rs = i;
        tr[i].fa = pos;
        st[++len] = i;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>tr[i].val;
        tr[i].pri = n - tr[i].val + 1; // 数小的优先级大
    }
    build();
    ll ans1 = 0, ans2 = 0;
    for(ll i=1;i<=n;i++){
        ans1 ^= i*(tr[i].ls+1);
        ans2 ^= i*(tr[i].rs+1);
    }
    cout<<ans1<<' '<<ans2<<'\n';
    return 0;
}