笛卡尔树

chenhanzheapple · 2025-07-04 21:38:42 · 算法·理论

定义

有 n 个节点。节点 i 为一个键值对 (x_i,y_i)，其中 x_i 不重复，y_i 不重复。

对于每个叶子节点 i，设其左儿子为 l_i，右儿子为 r_i，则满足：x_{l_i} < x_{r_i},y_i<y_{l_i},y_i<y_{r_i}。

建树

称一个笛卡尔树从根节点一直沿右子树走，直到叶节点上的路径为“右链”。下图红框为“右链”。

容易发现右链的性质：对于每个点，它仅会进出右链一次，即每个点仅会在右链中存在一段时间。

我们考虑将元素按下标顺序依次插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这棵树的右链的末端。于是我们执行这样一个过程，从下往上比较右链节点与当前节点 u 的 w，如果找到了一个右链上的节点 x 满足 w_x<w_u，就把 u 接到 x 的右儿子上，而 x 原本的右子树就变成 u 的左子树。

因为右链的性质，所以可以用一个栈来维护右链。栈中维护当前笛卡尔树的右链上的节点。一个点不在右链上了就把它弹掉。容易发现每个点最多进栈一次，因此时间复杂度为 O(n)。

例题

P5854 【模板】笛卡尔树

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,top,ans,ans2;
int p[10000005],l[10000005],r[10000005],st[10000005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> p[i];
    }
    for(int i=1;i<=n;i++){
        while(top && p[st[top]]>=p[i]){
            top--;
        }
        if(!top){
            l[i] = st[top+1];
        }
        else{
            l[i] = r[st[top]];
            r[st[top]] = i;
        }
        st[++top] = i;
    }
    for(int i=1;i<=n;i++){
        ans^=i*(l[i]+1);
        ans2^=i*(r[i]+1);
    }
    cout << ans << " " << ans2;
    return 0;
}