struct tree

{

    int ls,rs,size,cnt,val;

}t[maxn];

//以下为加点

//size表示当前节点的子树大小和自己的大小的和，

//cnt表示当前节点代表的数有几个

void add(int now,int val)//now为当前遍历的点的编号，val为点权值

{

    t[now].size++;

    if(t[now].val==val)

    {

        t[now].cnt++;//多个相同值得点，不增加点了

        return;

    }

    if(t[now].val>val)

    {

        if(t[now].ls!=)

        {

            addedge(t[now].ls,val);

        }

        else

        {

            cnt++;

            t[cnt].size=;

            t[cnt].val=val;

            t[cnt].cnt=;

            t[now].ls=cnt;

        }

    }

    else

    if(t[now].val<val)//根据二叉查找树的性质来插值

    {

        if(t[now].rs!=)//如果不是叶子节点

        {

            addedge(t[now].rs,val);//向下寻找叶子节点再插入

        }

        else

        {

            cnt++;//cnt为点的编号

            t[cnt].size=;//找前驱的东西

            t[cnt].val=val;//存值

            t[cnt].cnt=;//有几个相同的值

            t[now].rs=cnt;//点的编号，右儿子加点

        }

    }

}

int getqianqu(int now,int val,int ans)

{

    if(t[now].val>=val)//如果当前值大于正在被寻找前驱的值

    {//那么可以判定：前驱一定是在它的左子树中

        if(t[now].ls==)//如果没有左子树

        {

            return ans;//当前值就是答案

        }

        else //否则

        {

            getqianqu(t[now].ls,val,ans);//在左子树中找答案

        }

    }

    else if(t[now].val<val)//如果当前值小于正在被寻找前驱的值

    {//那么可以判定：前驱一定在它的右子树中 ，一路小过来，小过了，往大值试探

        if(t[now].rs==)//如果没有右子树

        {

            if(t[now].val<val)//如果当前值小于正在被寻找前驱的值

            {

                return t[now].val;//在没有右子树的情况下，当前点就是前驱

            }

            else

            {

                return ans;//否则前面点就是前驱

            }

        }

        if(t[now].cnt!=)//删点之后..在treap里的操作，这里没有

        {

            return getqianqu(t[now].rs,val,t[now].val);

        }

        else

        {

            return getqianqu(t[now].rs,val,ans);

        }

    }

}

int gethouji(int now,int val,int ans)

{

    if(t[now].val<=val)//如果当前值大于正在被寻找前驱的值

    {

        if(t[now].rs==)//如果没有左儿子

        {

            return ans;

        }

        else

        {

            gethouji(t[now].rs,val,ans);

        }

    }

    else if(t[now].val>val)

    {

        if(t[now].ls==)

        {

            if(t[now].val>val)

            {

                return t[now].val;

            }

            else

            {

                return ans;

            }

        }

        if(t[now].cnt!=)

        {

            return gethouji(t[now].ls,val,t[now].val);

        }

        else

        {

            return gethouji(t[now].ls,val,ans);

        }

    }

}

//size表示当前节点的子树大小和自己的大小的和，

//cnt表示当前节点代表的数有几个

int nth(int now,int rank)

{

    if(now==)//0，没有值

    {

        return 0x7fffffff;

    }

    if(t[t[now].ls].size>rank)//如果左子树的子树的大小大于nth

    {

        return nth(t[now].ls,rank);//去找左子树

    }

    if(t[t[now].ls].size+t[now].cnt>=rank)//如果左子树的子树的大小+当前节点（重复节点）大于等于nth

    {

        return t[now].val;//那这个点就是nth

    }

    return nth(t[now].rs,rank-t[t[now].ls].size-t[now].cnt);//找子树中nth-子树大小的值

}

int valth(int now,int val)

{

    if(now)==)

    {

        return ;

    }

    if(val==t[now].val)

    {

        return t[t[now].ls].size+;

    }

    if(val<t[now].val)

    {

        return valth(t[now].ls,val);

    }

    return valth(t[now].rs,val)+t[t[now].ls].size+t[now].cnt;

}//基本同理于kth