Cartesian Tree

Cartesian Tree

struct CartesianTree
{
    static const int __=50005;

    struct node
    {
        int val,key,id,fa,lson,rson;

        void clear(){fa=lson=rson=0;}

        bool operator<(const node &b)const
        {
            return val<b.val;
        }
    }t[__];

    CartesianTree() {clear();}

    node& operator[](int x){return t[x];}

    int root;
    stack<int>S;

    void build(int n)
    {
        sort(t+1,t+n+1);
        for(int i=1;i<=n;++i)
        {
            while(!S.empty() && t[S.top()].key>t[i].key)
                S.pop();
            t[i].clear();
            if(S.empty())
            {
                t[root].fa=i;
                t[i].lson=root;
                root=i,S.push(i);
                continue;
            }
            t[i].lson=t[S.top()].rson;
            t[t[S.top()].rson].fa=i;
            t[S.top()].rson=i;
            t[i].fa=S.top();
            S.push(i);
        }
    }

    void clear(){for(root=0;!S.empty();S.pop());}
}ct;