洛谷p3369 treap

这是一个treap裸题，还可以用splay，替罪羊树，线段树等等写

treap是树和堆结合，可以方便的在O(log(n))期望时间内进行以下操作，因此treap又叫做名次树

插入x数
删除x数(若有多个相同的数，因只删除一个)
查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x，且最大的数)
求x的后继(后继定义为大于x，且最小的数)

#include<bits/stdc++.h>
#include<ext/rope>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;
using namespace __gnu_cxx;

const double g=10.0,eps=1e-7;
const int N=200000+10,maxn=100000+10,inf=0x3f3f3f;

struct Node{
    Node* ch[2];
    int r;//排名
    int v;//权值
    int s;//节点数
    int flag;
    Node()
    {
        ch[0]=ch[1]=NULL;
        r=rand();v=0;
        s=flag=1;
    }
};
Node *root;
void maintain(Node* &o)//更新当前结点子树的节点数
{
    o->s=o->flag;
    if(o->ch[0]!=NULL)o->s+=o->ch[0]->s;//左子树不为空就加上数量
    if(o->ch[1]!=NULL)o->s+=o->ch[1]->s;//右子树不为空就加上数量
}
void Rotate(Node* &o,int d)//d=0左旋，d=1右旋
{
    Node* k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    maintain(o);maintain(k);
    o=k;
}
void Insert(Node* &o,int d)
{
    if(o==NULL)//子树为空直接加上去
    {
        o=new Node;
        o->v=d;
        return ;
    }
    else if(o->v==d)//可能会相等
    {
        o->flag++;
        maintain(o);
        return ;
    }
    int d1=d>o->v ? 1:0;//判断搜索哪一颗子树
    Insert(o->ch[d1],d);
    if(o->ch[d1]->r > o->r)Rotate(o,d1^1);
    else maintain(o);
}
void Remove(Node* &o,int d)
{
    if(o==NULL)return ;
    if(o->v==d)
    {
        if(o->flag>1)o->flag--;//该节点有多个数
        else
        {
            if(o->ch[0]==NULL&&o->ch[1]==NULL)o=NULL;
            else if(o->ch[0]!=NULL&&o->ch[1]!=NULL)
            {
                if(o->ch[0]->r > o->ch[1]->r)Rotate(o,1),Remove(o->ch[1],d);
                else Rotate(o,0),Remove(o->ch[0],d);
            }
            else //有一个节点不为空，就拿另一个补上
            {
                if(o->ch[0]==NULL)o=o->ch[1];
                else o=o->ch[0];
            }
        }
        if(o!=NULL)maintain(o);
    }
    else //根据d的大小找左右子树
    {
        if(d < o->v)Remove(o->ch[0],d);
        else if(d > o->v)Remove(o->ch[1],d);
        if(o!=NULL)maintain(o);
    }
}
int kth(Node* o,int k)//查询排名为k的节点
{
    if(k<0||k > o->s||o==NULL)return 0;//不合法的情况
    int ss=0;//左子树的节点
    if(o->ch[0]!=NULL)ss=o->ch[0]->s;
    if(k>=ss+1&&k<=o->flag+ss)return o->v;
    if(ss>=k)return kth(o->ch[0],k);//左边够大了，从左边找
    else return kth(o->ch[1],k-ss-o->flag);
}
int Rank(Node* o,int k)//查询k的排名
{
    if(o==NULL)return 0;
    int ss=0;
    if(o->ch[0]!=NULL)ss=o->ch[0]->s;
    if(o->v==k)return ss+1;
    if(o->v > k)return Rank(o->ch[0],k);//向左搜
    else return ss+o->flag+Rank(o->ch[1],k);//加上左子树的节点
}
void qq(Node* o,int k,int &ans)
{
    if(o==NULL)return ;
    if(o->v < k)
    {
        ans=max(ans,o->v);
        if(o->ch[1]!=NULL)qq(o->ch[1],k,ans);
    }
    else
    {
        if(o->ch[0]!=NULL)qq(o->ch[0],k,ans);
    }
}
void hj(Node* o,int k,int &ans)
{
    if(o==NULL)return ;
    if(o->v > k)
    {
        ans=min(ans,o->v);
        if(o->ch[0]!=NULL)hj(o->ch[0],k,ans);
    }
    else
    {
        if(o->ch[1]!=NULL)hj(o->ch[1],k,ans);
    }
}
int main()
{
    srand(time(NULL));
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;  
        if(a==1)Insert(root,b);
        else if(a==2)Remove(root,b);
        else if(a==3)printf("%d
",Rank(root,b));
        else if(a==4)printf("%d
",kth(root,b));
        else if(a==5)
        {
            int ans=0;qq(root,b,ans);
            printf("%d
",ans);
        }
        else
        {
            int ans=1e9;hj(root,b,ans);
            printf("%d
",ans);
        }
    }
    return 0;
}
/*******************

********************/

View Code