前言

打了一场 \(\rm{codeforces}\) , 其中 F 使用了笛卡尔树, 看起来这个东西的优先级比矩快还高, 那就学一下

似乎这道题并没有使用很多笛卡尔树的性质, 但是 \(\rm{yishu2}\) 开了个专题, 这下不得不学了

笛卡尔树

之前预习的时候看了一下

首先复习一下二叉查找树的性质

• 每个节点拥有用于比较大小的键值
• 对于任意一个节点, 令 \(Val_i\) 表示 \(i\) 点的键值, 有 \(Val_{rightson} >(\geq) Val_{fa} >(\geq) Val_{leftson}\)
• 由上可知, 二叉查找树的中序排列为有序数组

然后我们知道的是, \(\rm{Treap}\) 这样一个数据结构, 即 "树堆" , 基于 "键值 + 优先级" 这样的方式来维护二叉树的平衡性, 再具体一点, 我们知道对于键值, \(\rm{Treap}\) 是一颗二叉查找树, 而对于优先级, \(\rm{Treap}\) 是一个堆

\(\rm{Treap}\) 具体如何保证二叉树的平衡性虽然不是现在最主要的部分, 但为了了解深一点, 我在这里同时介绍一下

关于笛卡尔树的前置 : \(\rm{Treap}\)

\(\rm{Treap}\) 树有一个很棒的性质, 即当每个节点的键值, 优先级确定且互不相同, 那么这样的一颗 \(\rm{Treap}\) 在形态上是确定唯一的, 书上用 \(x, y\) 坐标来解释

如何给定优先级, 使得 \(\rm{Treap}\) 平衡?

容易发现当随机给定优先级, 那么 \(\rm{Treap}\) 在期望上平衡

那么学都学了, 我们顺带也把插入键值不确定的新节点这一部分讲一讲, 这里只介绍旋转法

首先朴素插入键值, 然后用旋转法维护堆的性质不受影响, 余下的并不难理解

关于笛卡尔树

原理 \(\And\) 特性

当每个数的键值预先确定, 那么这就是笛卡尔树

常见的, 笛卡尔树主要用于处理一个确定的数列, 把位置看做键值, 把数值看做优先级, 笛卡尔树有如下性质

• 当你对笛卡尔树做中序遍历, 那么返回的结果就是原数列, 这个可以用划线法来理解, 这里不加赘述
• 如果按照大根堆来建树, 那么根节点的数值一定大于其子树中所有节点

建立笛卡尔树

你说的对, 但是如果你使用 \(\rm{Treap}\) 的方法建立笛卡尔树, 不仅会带来巨大的码量, 而且多出了一个 \(\log\) , 这不好

所以介绍单调栈 \(\mathcal{O} (n)\) 的建树, 具体怎么推得我不加阐述了, 只介绍做法

每次插入新的节点 (先按照键值排序, 只需要按照优先级调整上下位置), 其横向位置一定, 一定是在最右边, 我们只需要考虑最右链

我们用单调栈维护最右链, 这样每次插入的时候, 新儿子一定在最右链的末端

单调栈可以找到最右链中, 第一个优先级比插入点高的点, 记为 \(u\) (若没有, 代码中设计了一个虚根 \(0\), 其优先级为 \(+\infty\)) , 以及这个点原本的右儿子 (只会影响到右儿子, 因为处理的是最右链) , 那么这个点将霸占 \(u\) 的右儿子位置, 并且原来的点将成为这个点的左儿子

思路

正式进入这道题, 他要求按照小根堆来建树, 那么我们只需要在建树的时候, 把优先级的比较改一下即可

实现

#include "bits/stdc++.h"
const int MAXN = 1e7 + 20;
const int INF = 0x3f3f3f3f;
typedef long long ll;

namespace IO
{
    inline int read() {
        int f = 1, x = 0;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
            x = x * 10 + (ch - '0'), ch = getchar();
        return x * f;
    }
};
using namespace IO;

int n;

/*笛卡尔树*/
struct Cartesian_Tree
{
    struct node {
        int ls, rs, fa; // 位置信息
        int pri, key; // 优先级 & 键值

        bool operator < (const node& a) {
            return key < a.key;
        }
    } Tree[MAXN];

    /*建树*/
    void buildtree() {
        std::stack<int> MS; MS.push(0);
        for (int i = 1; i <= n; i++) {
            int pos = MS.top();
            while (!MS.empty() && Tree[pos].pri > Tree[i].pri) {
                pos = Tree[MS.top()].fa;
                MS.pop();
            }

            Tree[i].ls = Tree[pos].rs, Tree[Tree[i].ls].fa = i, Tree[pos].rs = i, Tree[i].fa = pos;
            MS.push(i);
        }
    }
} C_Tree;

/*计算题目要求的答案*/
void calc()
{
    ll ans1, ans2;
    for (ll i = 1; i <= n; i++) {
        ans1 = ((i == 1) ? i * (C_Tree.Tree[i].ls + 1ll) : (i * (C_Tree.Tree[i].ls + 1ll)) ^ ans1);
        ans2 = ((i == 1) ? i * (C_Tree.Tree[i].rs + 1) : (i * (C_Tree.Tree[i].rs + 1)) ^ ans2);
    }
    printf("%lld %lld", ans1, ans2);
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
        C_Tree.Tree[i].key = i, C_Tree.Tree[i].pri = read();
    C_Tree.Tree[0].fa = C_Tree.Tree[0].ls = C_Tree.Tree[0].rs = C_Tree.Tree[0].key = 0;
    C_Tree.Tree[0].pri = INF;

    /*对标签排序 (本题中不需要)*/
    // std::sort(C_Tree.Tree + 1, C_Tree.Tree + n + 1);

    C_Tree.buildtree();

    calc();

    return 0;
}