笛卡尔树学习笔记

2021年11月24日 阅读数:3
这篇文章主要向大家介绍笛卡尔树学习笔记,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

前言

首先膜拜 \(fls\) 成为全场惟一 AK 了 《板子大师赛》 的选手。CCCCCCCCCOrzc++

《板子大师赛》中出现了 P5854 【模板】笛卡尔树。在 \(CSP2021\) 初赛以前 \(zzz\) 学长就给咱们讲过如何建笛卡尔树,初赛中更是考到了单调栈建笛卡尔树的完形填空题。spa

然而本蒟蒻太蒻了,洛谷上的模板题都没有作过。code

比赛中第一次写,并成功 A 掉了模板qwqblog

笛卡尔树

定义

无相同元素的数列构造出的笛卡尔树具备下列性质:排序

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

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

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

下面再举一个例子:it

假设原序列:table

1 2 3 4 5 6 7 8 9 10 11
9 3 7 1 8 12 10 20 15 18 5

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

cartesian-tree1.png (648×621) (oi-wiki.org)

(图源自维基百科)

构建

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

这里以 洛谷模板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\_ \]