笛卡尔树 笛卡尔树（Cartesian tree）是一种树形数据结构，每个节点都是一个区间，树的根节点表示整个区间，左儿子表示区间的左半部分，右儿子表示区间的右半部分。 笛卡尔树可以通过单调栈 \(O(n)\) 静态建造。 例题 P2659美丽的序列 题意 找出一个序列的所有子段中子段长度乘段内元素最小值的最大值。 思路 我们需要找出所有子段中贡献最大的，并且一个...

线段树在维护区间时可以维护任何区间信息，比如，一个单调栈。 P4198 楼房重建 题意：维护全局最大上升序列大小。 更新 线段树当前节点存储整个区间的最大值，对于该题，左子树的区间答案可以直接继承，然后用左子树区间的最大值查询右子树的答案并记录在该节点上。 123456void update(const int &x,const double &k,const in...