本篇笔记是建立在treap相关知识的基础上的
由于本人水平较菜，笔记中定有晦涩难懂之处，望给出指导意见
定义：
笛卡尔树是一种同时满足BST和堆性质的树形数据结构，树上的每个节点通过fix（满足堆性质）和value（满足BST性质）两个数据来维护。
显然，我们将value作为关键字进行排序后，将节点一一加入到笛卡尔树中，那么通过中序遍历得到的序列仍为排序好的序列。
可以证明，当fix和value一定时，笛卡尔树是唯一的
O(n)构造法：
假设我们用小根堆来维护笛卡尔树，用每个数在数组中的位置来表示其对应的value值，那么如何通过原数组构造一棵完整的笛卡尔树呢？
由BST的性质可以得知，我们最后加入的节点一定在根节点或者右链上的叶子节点
和treap一样，我们当然可以先将这个节点放在原对应叶子节点的右儿子上，然后判断是否满足堆性质，不满足则进行旋转，但是显然我们没有这个必要，因为对于新加入的节点来说，如果无法满足堆性质，一定会进行左旋转
显然，我们实质上就是将右链上的某个节点旋转到了新节点的左子树上
而这个节点的位置，就是第一个小于新节点的节点的右子节点，在旋转过后，这个位置被新节点所代替了
假设第一个小于新节点i的节点的位置为pre，那么关键代码只有两行：
tree[i].lc=tree[pre].rc;
tree[pre].rc=i;
显然，加入新节点的前后，右链始终是一个单调递增序列
从上述过程来看，我们只需要维护右链的单调递增就行了
这个维护过程用单调栈来实现即可，最后栈底所对应的节点即为笛卡尔树的根节点
每个元素仅进栈1次，出栈1或0次，旋转1或0次，因此整体上时间复杂度是O(n)的
struct node{ int lc,rc; }tree[500010]; inline int read(){ int x=0,y=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-')y=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*y; } void init(){ n=read(); for (int i=1;i<=n;i++) a[i]=read(); } void build_tree(){ stack[0]=0; for (int i=1;i<=n;i++){ while (top&&a[stack[top]]>a[i]) top--; int pre=stack[top]; tree[i].lc=tree[pre].rc; tree[pre].rc=i; stack[++top]=i; } }
这样的构造方法仅适用于value单调的时候，当value不单调时，排序后再建树即可