nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

笛卡尔树

这个笛卡尔树没写出来,气死了
他是二叉树,他是堆,二叉树中序遍历的结果就是数组a

笛卡尔树的构造

先看一个简单的笛卡尔树

我们使用增量构建笛卡尔树来完成,就和增量构建后缀自动机一样容易。我们来对x分类讨论如果x比5小怎么样,如下

如果x在5和7之间

如果x在7和9之间

如果x比9大呢

我们不难发现,每当增加一个新的值的时候,笛卡尔树变化的一定只有从根一直向右走的路径,我们可以想出一个很简单的方法,每次新增加值a[i+1]的时候,让他不断和右链比较,找到lower_bound的地方,然后插入到那去就可以了。
进一步发现,上诉代码需要维护指向父亲的指针,我们考虑到用一个栈来维护右链,栈低为根,栈顶为叶子,在弹栈的时候维护右儿子指针,在压栈的时候维护左儿子指针即可。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
int a[N]; // a[1], a[2], a[3], a[4] ... a[n]
int l[N],r[N]; // 0为空指针
int s[N],top; //栈
void build(){
s[++top]=1;// 把起点压栈
for(int i=2;i<=n;i++){
//r[i]=l[i]=0;
while(top&&a[s[top]]<=a[i]) l[i]=s[top--]; //弹栈的时候维护左儿子指针
if(top) r[s[top]]=i; // 压栈的时候维护右儿子指针
s[++top]=i;
} // 返回的时候栈顶为根
}