传送门
介绍什么是笛卡尔树
笛卡尔树是一种二叉树，每一个结点由一个键值二元组 ( 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是数组下标,因此我们直接从左到右直接插入即可
现在我们许哟啊维护的是满足二叉树的性质
首先我们维护二叉树的性质,肯定每次都是往右链进行插入,但是同时我们还需要满足堆的性质
- 如果 w w w 大于当前右链末端点的 w w w那么直接插入到右端末链(小根堆)
- 如果 w w w小于当前右链末端点的 w w w,那么当前节点要继续往上找,直到遇到第一种情况
如果我们找到了一个 w j < w u w_j
