『学习笔记』笛卡尔树

模板题：P5854 【模板】笛卡尔树

# 定义

无相同元素的数列构造出的笛卡尔树具有下列性质：

1. 结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素
2. 中序遍历（in-order traverse）笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小，右子树结点所对应数列元素下标比该结点所对应元素下标大。
3. 树结构存在堆序性质，即任意树结点所对应数值大 / 小于其左、右子树内任意结点对应数值

根据堆序性质，笛卡尔树根结点为数列中的最大 / 小值，树本身也可以通过这一性质递归地定义：根结点为序列的最大 / 小值，左、右子树则对应于左右两个子序列，其结点同样为两个子序列的最大 / 小值。因此，上述三条性质唯一地定义了笛卡尔树。若数列中存在重复值，则可用其它排序原则为数列中相同元素排定序列，例如以下标较小的数为较小，便能为含重复值的数列构造笛卡尔树。

—— 源自笛卡尔树_百度百科

下面再举一个例子：

假设原序列：

那么构建出来的笛卡尔树是这样的：

（图源自维基百科）

# 构建

上面已经提到过了，用单调栈来构建。

这里以 洛谷模板 P5854 【模板】笛卡尔树 为例，具体地来说一说如何构建笛卡尔树。

我们用维护极右链的过程来建树。

Q：极右链是什么？

A：在树上从根节点一直向右儿子跑，就是上图中的 1 和 5，这是已经构造好了的笛卡尔树的极右链。

Q：极右链有什么性质？

A：在这道题目中，极右链是一个递增的序列。

Q：为什么构造极右链就可以构造出笛卡尔树，以及极右链如何构造？

A：这就是本文的重点了，我们来谈一谈维护极右链的过程。

首先用一个单调递增的单调栈维护极右链，按顺序枚举原数列中的每一位，与栈顶比大小，假设当前枚举到 $x$ ，且栈顶元素为 $k$：

• $x > k$：$x$ 直接入栈，并成为 $k$ 的右儿子。
• $x \leq k$：此时一直弹栈，直到栈顶元素 $k' < x$，停止弹栈，$x$ 入栈，成为 $k'$ 的右儿子，并把最后一个被弹出的元素 $last$ 从 $k'$ 的右儿子转变到 $x$ 的左儿子。

先是 9：此时栈中没有元素，9 入栈。此时栈：

$$9$$

第二位是 3 ：我们发现 3 比 9 小，弹栈，并把 9 变成 3 的左儿子，3 入栈。

$$3$$

第三位是 7 ：7 比 3 大，7 直接入栈，并把 7 变成 3 的右儿子。

$$3\ |\ 7$$

第四位是 1 ：1 比 7 小，7 被弹出，1 比 3 小，3 被弹出，此时栈空，把 3 接到 1 的左儿子上，然后 1 入栈。

$$1$$

第五位 8 ：比 1 大，入栈，并把 8 接到 1 的右儿子上。

$$1\ |\ 8$$

第六位 12 ：比 8 大，同样入栈，并把 12 接到 8 的右儿子上。

$$1\ |\ 8\ |\ 12$$

第七位是 10 ：比 12 小，12 被弹出：比 8 大，10 入栈，并成为 8 的新右儿子，再把 12 从原本 8 的右儿子变成 10 的左儿子。

$$1\ |\ 8\ |\ 10$$

第八位是 20 ：比 10 大，入栈， 20 成为 10 的右儿子上。

$$1\ |\ 8\ |\ 10\ |\ 20$$

第九位是 15 ：15 比 20 小，20 被弹出；比 10 大，15 入栈，成为 10 的新右儿子，并把 20 变成 15 的左儿子。

$$1\ 8\ 10\ 15$$

第十位是 18 ：大于 15，直接入栈，18 成为 15 的右儿子。

$$1\ |\ 8\ |\ 10\ |\ 15\ |\ 18$$

最后一位是 5 ：18，15，10，8 全都比 5 大，依次被弹出，1 比 5 小，5 入栈，成为 1 的新右儿子，并把 8 从 1 的右儿子变成 5 的左儿子。

至此，上面的样例就模拟完了，如果您认真地模拟了一遍，一定会明白构造笛卡尔树的过程的，并理解了构造极右链过程的奥妙。

板子题就解决了，以后我再做到什么笛卡尔树的例题，再更博吧 qwq

# 代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

inline int read(){

    int x = 0;

    char ch = getchar();

    while(ch < '0' || ch > '9') ch = getchar();

    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();

    return x;

}

const int N = 1e7 + 10;

int n;

ll ansl, ansr;

int a[N];

struct Tree{

    int l, r;

}t[N];

int stk[N], top;

int main(){

    n = read();

    for(int i = 1, res = 0; i <= n; ++i, res = 0){

        a[i] = read();

        while(top && a[stk[top]] > a[i]) res = stk[top--];// 弹栈，并用 res 记录最后一个被弹出的元素

        t[i].l = res;// 最后一个被弹出的元素 成为 当前正在处理的元素的左儿子

        t[stk[top]].r = i;// 当前正在处理的元素 成为 当前栈顶的右儿子

        stk[++top] = i;// 当前元素入栈

    }

    for(int i = 1; i <= n; ++i)

        ansl ^= ((ll)i * (t[i].l + 1ll)), ansr ^= ((ll)i * (t[i].r + 1ll));

    printf("%lld %lld\n", ansl, ansr);

    return 0;

}

$$\_EOF\_$$