笛卡尔树 学习笔记

作者: xht37 分类: 笔记 发布时间: 2019-12-27 18:28

点击数:310

碰到好多次了,系统的整理一下。

定义

笛卡尔树跟 Treap 的定义是一样的:

  • 二叉树
  • 每个节点有一个键值 $(k,w)$。
  • $k$ 满足二叉搜索树的性质。
  • $w$ 满足二叉堆的性质。

严格意义上讲,Treap 是 $w$ 随机的笛卡尔树。

通常我们可以对一个序列构建笛卡尔树:以下标为 $k$,以元素为 $w$。

这样构建的笛卡尔树的每一个子树都对应着序列的一个区间。

构建

由于对 $k$ 排序后,每次一定是在笛卡尔树的右链上插入一个新的元素。

因此我们可以利用单调栈维护右链。每当一个新节点找到一个位置插入后,把原来那个位置上的子树作为新节点的左儿子即可。

总时间复杂度 $\mathcal O(n)$。

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

const int N = 1e7 + 7;
int n, a[N], s[N], t, l[N], r[N];
ll L, R;

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        rd(a[i]);
        int k = t;
        while (k && a[s[k]] > a[i]) --k;
        if (k) r[s[k]] = i;
        if (k < t) l[i] = s[k+1];
        s[++k] = i, t = k;
    }
    for (int i = 1; i <= n; i++) L ^= 1ll * i * (l[i] + 1), R ^= 1ll * i * (r[i] + 1);
    print(L, ' '), print(R);
    return 0;
}

【例题】P1377 [TJOI2011]树的序

这题实际上是求以元素为 $w$、以下标为 $k$ 的笛卡尔树的先序遍历。

const int N = 1e5 + 7;
int n, a[N], s[N], t, l[N], r[N];
ll L, R;

void dfs(int x) {
    if (x) print(x, ' '), dfs(l[x]), dfs(r[x]);
}

int main() {
    rd(n);
    for (int i = 1, x; i <= n; i++) rd(x), a[x] = i;
    for (int i = 1; i <= n; i++) {
        int k = t;
        while (k && a[s[k]] > a[i]) --k;
        if (k) r[s[k]] = i;
        if (k < t) l[i] = s[k+1];
        s[++k] = i, t = k;
    }
    dfs(s[1]);
    return 0;
}

参考资料

一条评论
  • ql12345

    2020年8月20日 上午7:53

    “树的序”那道题应该是下标为w,元素为k吧

发表评论

电子邮件地址不会被公开。 必填项已用*标注