视频字幕
笛卡尔树是一种特殊的数据结构，它既满足二叉搜索树的性质，又满足堆的性质。在信息学竞赛中，笛卡尔树常用于解决区间最值查询等重要问题。
笛卡尔树有两个重要性质。第一，它满足二叉搜索树的性质，即中序遍历会得到原始序列。第二，它满足堆的性质，每个节点的值都小于或等于其父节点的值。构建笛卡尔树就是基于这两个性质进行的。
构建笛卡尔树的步骤如下：首先从左到右扫描序列。然后维护一个单调递增的栈，用于存储可能的父节点。对于每个新元素，我们需要找到它在栈中的正确位置。最后调整树结构，确保同时满足二叉搜索树和堆的性质。
单调栈的维护是构建笛卡尔树的关键步骤。当当前元素比栈顶元素大时，直接入栈。当当前元素比栈顶元素小时，需要弹出栈顶元素，直到栈顶元素小于当前元素。然后新元素成为被弹出节点的父节点或右子节点，以满足笛卡尔树的两种性质。
我们通过一个具体例子来演示构建过程。给定序列二，三，四，五，七。插入二时，栈为空，直接入栈。插入三时，因为三大于二，也直接入栈。后续的四，五，七都比栈顶元素大，所以都直接入栈。最终我们得到一个满足笛卡尔树性质的结构。
笛卡尔树的构建具有线性时间复杂度O(n)。这是因为每个元素最多只会入栈和出栈一次。所有栈操作的总时间与元素个数成正比。这使得笛卡尔树成为处理序列相关问题的高效数据结构。
笛卡尔树的一个重要应用是解决RMQ问题，即区间最值查询。通过构建序列的笛卡尔树，我们可以将RMQ问题转化为树上最近公共祖先问题。这种转化利用了树结构的性质，能够高效地解决问题。
总结一下，笛卡尔树是一种同时满足二叉搜索树和堆性质的重要数据结构。它的构建使用单调栈维护，具有线性时间复杂度。笛卡尔树可以用于解决RMQ等经典问题，在信息学竞赛中具有重要应用价值。