笛卡尔树就是你给两维限制，一维堆R，一维二叉搜索树K，平地拔起一棵Treap，最广范的应用：用LCA求区间最值，建Treap，还有个什么范围top k我表示并不会查都查不到。它最妙最高的地方在于用栈来建树：我们可以先排序K然后一个个插入，那么我们都是最右端，横容易被卡，那么我们不从上到下，我们从下到上，用栈维护，那就把时间复杂度从O(n^2)降到O(n)，具体过程见下图从图一到图二就是这么一个过程，我们在把K为13的点插入时要找到一个合适的位置，上比他大，下比他小（假设大根堆）

下面见代码

#include
     
      #include
      
       #define MAXN 500010using namespace std;inline int read(){  int sum=0;  char ch=getchar();  while(ch<'0'||ch>'9')ch=getchar();  while(ch>='0'&&ch<='9')  {    sum=(sum<<1)+(sum<<3)+ch-'0';    ch=getchar();  }  return sum;}struct Treap{  int key,r;  Treap *ch[2];}*stack[MAXN],node[MAXN],*root;int top;int n;int comp(const Treap a,const Treap b){  return a.key
       
        r>node[i].r)       last=stack[top--];      if(top)stack[top]->ch[1]=node+i;      node[i].ch[0]=last;      stack[++top]=node+i;   }   root=stack[1];}void dfs(Treap *p){  if(!p)return;  printf("%d ",p->key);  dfs(p->ch[0]);  dfs(p->ch[1]);}int main(){    int __size__=128<<20;    char *__p__=(char*)malloc(__size__)+__size__;    __asm__("movl %0, %%esp\n"::"r"(__p__));    freopen("treap.in","r",stdin);    freopen("treap.out","w",stdout);    Init();    Build();    dfs(root);    return 0;}