“不会线性可以用线段树睡过去”

笛卡尔树

0x01. 什么是笛卡尔树

定义(摘自OI wiki)

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 \((k,w)\) 构成。要求 \(k\) 满足二叉搜索树的性质，而 \(w\) 满足堆的性质。如果笛卡尔树的 \(k,w\) 键值确定，且 \(k\) 互不相同，\(w\) 也互不相同，那么这棵笛卡尔树的结构是唯一的。

浅显地说：

一个小根堆（或大根堆），其中序遍历为原序列。

0x02. 为什么要使用笛卡尔树

性质（以小根堆为例）：

1. 以 \(u\) 为根的子树是一段连续的区间, 且 \(u\) 是这段区间的最小值。
2. 任意区间 \([l, r]_{min} = LCA(l, r)\)

建树复杂度：

• 考虑线段树维护区间最小值，查询 \(O(log_n)\), \(n\) 个数总计 \(O(nlog_n)\)
• 考虑单调栈维护单增序列，复杂度 \(O(n)\)

0x03. 具体实现与代码

P5854 【模板】笛卡尔树

线段树实现笛卡尔树：

注意：此题数据范围 \(n \le1e7\) 无法通过

单调栈实现笛卡尔树：