## 定义 > 笛卡尔树是一种二叉树，每一个结点由一个键值二元组 $(k,w)$ 构成。要求 $k$ 满足二叉搜索树的性质，而 $w$ 满足堆的性质。一个有趣的事实是，如果笛卡尔树的 $k,w$ 键值确定，且 $k$ 互不相同，$w$ 互不相同，那么这个笛卡尔树的结构是唯一的。上图： > >  > > （图源自维基百科） > > 上面这棵笛卡尔树相当于把数组元素值当作键值 $w$，而把数组下标当作键值 $k$。显然可以发现，这棵树的键值 $k$ 满足二叉搜索树的性质，而键值 $w$ 满足小根堆的性质。 > > 其实图中的笛卡尔树是一种特殊的情况，因为二元组的键值 $k$ 恰好对应数组下标，这种特殊的笛卡尔树有一个性质，就是一棵子树内的下标是连续的一个区间（这样才能满足二叉搜索树的性质）。更一般的情况则是任意二元组构建的笛卡尔树。 以上摘自[OI-wiki](https://oi-wiki.org/ds/cartesian-tree/) ## 建树 我们来看一道模板题： 题目：[P5854 【模板】笛卡尔树](https://www.luogu.com.cn/problem/P5854) > 给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。 > > 即构建一棵二叉树，满足： > > 1. 每个节点的编号满足二叉搜索树的性质。 > 2. 节点 $i$ 的权值为 $p_i$ ，每个节点的权值满足小根堆的性质。 我们令二元组为 $(i, p_i)$，$i$ 对应 $k$，$p_i$ 对应 $w$。 ### 解法 1（不能过） 我们先考虑一种比较暴力的做法。 因为 $w$ 满足堆的性质，所以根节点一定是这个子树内最小的节点，所以我们每次在区间内查询最小值，即为这个区间的根节点，因为 $k$ 需要满足二叉搜索树的性质，所以左儿子需要指向删除这个点后的左区间，右儿子指向右区间。 于是，没此只要查询区间最小值，使用RMQ在 $O(n\log n)$ 的时间内即可完成，但是过不了。 ### 解法二 我们先考虑二叉搜索树性质，因为本题中 $k$ 就是 $i$，也就是说这棵树 $k$ 的中序遍历是上升的。 我们只需要从左往右插入每个元素。 如果当前要插入的元素的 $w$ 值大于当前最右边的节点的 $w$ 值，直接插入在最右边节点的右儿子上，这样也满足了堆性质，如图：  如果当前插入的元素小于最右边的结点的值，那么显然它是要在上面的，我们找到最右结点的父亲，如果他父亲节点也小于呢？我们就不断往上跳，直到有一个节点，当前的 $w$ 比这个节点大，那当前节点就可以成为这个结点的右儿子，下面那些比他大的节点需要满足二叉搜索树性质，需要成为它的左儿子，然后它们都不再会用到，如下图：  下面有一个录制的过程，可以帮助更好的理解（Amihood Amir）：  这样，每个结点只会被访问一次，只要用一个栈维护，时间复杂度：$O(n)$ #### 代码 (用stl中的stack维护单调栈) ```c++ #include <cstdio> #include <cctype> #include <stack> #define int long long using namespace std; const int N=1e7+10; int n, a[N], l[N], r[N], ans1, ans2; stack<int> s; int read() { int x=0, f=0; char ch=getchar(); while (!isdigit(ch)) f|=ch=='-', ch=getchar(); while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar(); return f ? -x : x; } signed main() { n=read(); for (int i=1; i<=n; i++) { a[i]=read(); while (!s.empty() && a[s.top()]>a[i]) l[i]=s.top(), s.pop(); if (!s.empty()) r[s.top()]=i; s.push(i); } for (int i=1; i<=n; i++) { ans1^=(i*(l[i]+1)); ans2^=(i*(r[i]+1)); } printf("%lld %lld\n", ans1, ans2); return 0; } ``` ## 参考 1. [OI-wiki](https://oi-wiki.org/ds/cartesian-tree/) Loading... ## 定义 > 笛卡尔树是一种二叉树，每一个结点由一个键值二元组 $(k,w)$ 构成。要求 $k$ 满足二叉搜索树的性质，而 $w$ 满足堆的性质。一个有趣的事实是，如果笛卡尔树的 $k,w$ 键值确定，且 $k$ 互不相同，$w$ 互不相同，那么这个笛卡尔树的结构是唯一的。上图： > >  > > （图源自维基百科） > > 上面这棵笛卡尔树相当于把数组元素值当作键值 $w$，而把数组下标当作键值 $k$。显然可以发现，这棵树的键值 $k$ 满足二叉搜索树的性质，而键值 $w$ 满足小根堆的性质。 > > 其实图中的笛卡尔树是一种特殊的情况，因为二元组的键值 $k$ 恰好对应数组下标，这种特殊的笛卡尔树有一个性质，就是一棵子树内的下标是连续的一个区间（这样才能满足二叉搜索树的性质）。更一般的情况则是任意二元组构建的笛卡尔树。 以上摘自[OI-wiki](https://oi-wiki.org/ds/cartesian-tree/) ## 建树 我们来看一道模板题： 题目：[P5854 【模板】笛卡尔树](https://www.luogu.com.cn/problem/P5854) > 给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。 > > 即构建一棵二叉树，满足： > > 1. 每个节点的编号满足二叉搜索树的性质。 > 2. 节点 $i$ 的权值为 $p_i$ ，每个节点的权值满足小根堆的性质。 我们令二元组为 $(i, p_i)$，$i$ 对应 $k$，$p_i$ 对应 $w$。 ### 解法 1（不能过） 我们先考虑一种比较暴力的做法。 因为 $w$ 满足堆的性质，所以根节点一定是这个子树内最小的节点，所以我们每次在区间内查询最小值，即为这个区间的根节点，因为 $k$ 需要满足二叉搜索树的性质，所以左儿子需要指向删除这个点后的左区间，右儿子指向右区间。 于是，没此只要查询区间最小值，使用RMQ在 $O(n\log n)$ 的时间内即可完成，但是过不了。 ### 解法二 我们先考虑二叉搜索树性质，因为本题中 $k$ 就是 $i$，也就是说这棵树 $k$ 的中序遍历是上升的。 我们只需要从左往右插入每个元素。 如果当前要插入的元素的 $w$ 值大于当前最右边的节点的 $w$ 值，直接插入在最右边节点的右儿子上，这样也满足了堆性质，如图：  如果当前插入的元素小于最右边的结点的值，那么显然它是要在上面的，我们找到最右结点的父亲，如果他父亲节点也小于呢？我们就不断往上跳，直到有一个节点，当前的 $w$ 比这个节点大，那当前节点就可以成为这个结点的右儿子，下面那些比他大的节点需要满足二叉搜索树性质，需要成为它的左儿子，然后它们都不再会用到，如下图：  下面有一个录制的过程，可以帮助更好的理解（Amihood Amir）：  这样，每个结点只会被访问一次，只要用一个栈维护，时间复杂度：$O(n)$ #### 代码 (用stl中的stack维护单调栈) ```c++ #include <cstdio> #include <cctype> #include <stack> #define int long long using namespace std; const int N=1e7+10; int n, a[N], l[N], r[N], ans1, ans2; stack<int> s; int read() { int x=0, f=0; char ch=getchar(); while (!isdigit(ch)) f|=ch=='-', ch=getchar(); while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar(); return f ? -x : x; } signed main() { n=read(); for (int i=1; i<=n; i++) { a[i]=read(); while (!s.empty() && a[s.top()]>a[i]) l[i]=s.top(), s.pop(); if (!s.empty()) r[s.top()]=i; s.push(i); } for (int i=1; i<=n; i++) { ans1^=(i*(l[i]+1)); ans2^=(i*(r[i]+1)); } printf("%lld %lld\n", ans1, ans2); return 0; } ``` ## 参考 1. [OI-wiki](https://oi-wiki.org/ds/cartesian-tree/) 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏