本来早就该学笛卡尔树了，但暑假打模拟赛就一直没学成。于是就打算先不学了，结果又发现后面有个笛卡尔树专题，只好来学学。
笛卡尔树是一棵二叉树，每个点有一个键和一个值，键满足堆的性质，值满足二叉搜索树的性质。没错当键随即时，这就是个 Treap。
如果值单调递增，那么就可以线性建树。具体地，维护整棵树的右链。右链就是从根开始不停往右儿子走的链。因为值递增所以新加的点一定会在右链中。假设新加入的点 \(u\) 值为 \(k\) 键为 \(w\)，记为 \((k,w)\)，则从右链下端开始不断向上比较，找到一个 \(x\) 使它的键小于 \(w\)。那么 \(u\) 就成为 \(x\) 的右儿子，\(x\) 原本的右儿子就成为 \(u\) 的左儿子。放张图更直观（红色方框即为右链）：
图中 insert 后面括号里的是值，图上圆圈里的是键。显然用单调栈来维护右链就行了。