笛卡尔树

· · 个人记录

变量

函数

代码

struct Dicar{
    int a[N],ls[N],rs[N];
    int z[N],top;
    void build(int n){
        top=0;
        memset(ls,0,sizeof(ls));
        memset(rs,0,sizeof(rs));
        for(int i=1;i<=n;i++){
            int tmp=top;
            while(tmp&&a[z[tmp]]>a[i])
                tmp--;
            if(tmp)
                rs[z[tmp]]=i;
            if(tmp<top)
                ls[i]=z[tmp+1];
            z[++tmp]=i;
            top=tmp;
        }
    }
}tree;