笛卡尔树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
namespace CartesianTree
{
    int N,val[MAX],lson[MAX],rson[MAX];
    int stk[MAX],top;
    inline void build()
    {
        for(int i=1;i<=N;++i)
        {
            int k=top;
            while(k&&val[stk[k]]>val[i]) --k;
            if(k) rson[stk[k]]=i;
            if(k<top) lson[i]=stk[k+1];
            stk[++k]=i,top=k;
        }
    }
}