\(\text{Part 1.}\) 笛卡尔树是什么和其构建方法
笛卡尔树是一个二叉树,对于这棵树上的每一个节点,其都有两个值 \((k,w)\),其中 \(k\) 满足二叉搜索树的性质,\(w\) 满足堆的性质。如果所有的 \(k\) 和所有的 \(w\) 均不相同,那么笛卡尔树就是唯一的。
而根据如上的定义,Treap 也是一颗笛卡尔树。
下面就是一个笛卡尔树的例子:
其中对于节点 \(i\),他的两个键值就是 \((i,a_i)\)。而如果在笛卡尔树中 \(w\) 满足小根堆的性质,那么我们称这棵笛卡尔树为小根笛卡尔树。
那么他是如何构建的呢?现在考虑对于一个序列 \(a\) 建笛卡尔树。
由于下下标肯定是单增的,所以新插入的点只能是已前面点的右儿子、前面点只能是它的左儿子。
所以此时考虑使用单调栈维护一个权值单调递增的下标序列。那么在插入一个新点的时候,这个点就是第一个比它小的点的右儿子。比这个新点大的最后一个点作为这个新点的左儿子。
code:
void build()
{for(int i = 1;i <= n;i++){int pos = 0;while(top && a[stk[top]] > a[i])pos = stk[top],top--;if(top)ch[stk[top]][1] = i;ch[i][0] = pos;stk[++top] = i;}
}
注意笛卡尔树的模板题卡常。