[luogu] P5854 【模板】笛卡尔树 笛卡尔树

前言

传送门

介绍

什么是笛卡尔树

笛卡尔树是一种二叉树，每一个结点由一个键值二元组 ( k , w ) (k,w) (k,w)构成。要求 k k k 满足二叉搜索树的性质，而 w w w 满足堆的性质。

建树

给定一个序列 A [ ] A[] A[]

我们考虑建立的树节点为 ( i , A i ) (i,A_i) (i,Ai​)

即 i i i对应 k k k, A i A_i Ai​对应 w w w

因为 k k k是数组下标,因此我们直接从左到右直接插入即可

现在我们许哟啊维护的是满足二叉树的性质

首先我们维护二叉树的性质,肯定每次都是往右链进行插入,但是同时我们还需要满足堆的性质

1. 如果 w w w 大于当前右链末端点的 w w w那么直接插入到右端末链(小根堆)
2. 如果 w w w小于当前右链末端点的 w w w,那么当前节点要继续往上找,直到遇到第一种情况

如果我们找到了一个 w j < w u w_j