nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

笛卡尔树

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

笛卡尔树的构造

先看一个简单的笛卡尔树

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

如果x在5和7之间

如果x在7和9之间

如果x比9大呢

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

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;
  } // 返回的时候栈顶为根
}

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： fightinggg
• 本文链接： http://fightinggg.github.io/yilia/yilia/Q80DTB.html
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！