笛卡尔树
以下标作为val，数值作为key，满足堆性质的平衡树(treap是权值随机的笛卡尔树)
cpp
int stk[N],top,ls[N],rs[N],a[N];
void solve(){
for(int i=1;i<=n;i++){
cur=top;
while(cur&&a[stk[cur]]>a[i])cur--;
if(cur)rs[stk[cur]]=i;
if(cur<top)ls[i]=stk[cur+1];
stk[++cur]=i;
top=cur;
}
}