浅谈笛卡尔树

笛卡尔树（Cartesian Tree），是一种二叉树，每个节点都有两个信息 \((x_i,y_i)\)，其中把 \(x_i\) 单独拎出来看是一棵二叉搜索树（\(ls_u<u<rs_u\)），而把 \(y_i\) 拎出来是一个小根堆（\(u<ls_u,rs_u\)）。

废话不说，先看一道模板题 P5854 【模板】笛卡尔树，这道题题意就是说：

给你一个排列 \((p_1,p_2,\cdots,p_n)\)，构造信息为 \((i,p_i)\) 的笛卡尔树。

这道题可以 \(p_1\) 到 \(p_n\) 依次加进来（事实上所有建笛卡尔树都是先按 \(x_i\) 排序的，只不过这个 \(i\) 本来就是有序的）。

然后你可以想到每次肯定是尽量往右插，这样才能得到结果。一个事实是，笛卡尔树的构建是唯一的（笔者暂时并未想清楚原因，欢饮评论区留言)。

更具体地来说，每一次找到一个最大的比当前要插的数小的最大的点，设为 \(v\)，则将 \(v\) 的右儿子设为当前点（如果 \(v\) 存在的话）。如果 \(v\) 已经有右儿子了的话，就将当前的点接在 \(v\) 和 \(rs_v\) 中间。

代码如下（貌似要进行一些卡常？）：

// AC

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7 + 10;
int n, p[N], stk[N], tp = 0, cur;
int ch[N][2]; // 0: left son, 1: right son

inline int read() {
    int x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x;
}

int main() {
    // ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    n = read();
    for(int i = 1; i <= n; i++) {
        p[i] = read();
        cur = tp;
        while(cur > 0 && p[stk[cur]] > p[i]) --cur;
        if(cur > 0) ch[stk[cur]][1] = i;
        if(cur < tp) ch[i][0] = stk[cur + 1];
        stk[tp = ++cur] = i;
    }
    long long ans1 = 0, ans2 = 0;
    for(int i = 1; i <= n; i++) {
        ans1 ^= 1LL * i * (ch[i][0] + 1);
        ans2 ^= 1LL * i * (ch[i][1] + 1);
    }
    printf("%lld %lld\n", ans1, ans2);
    return 0;
}