还没写完 因为我还没学明白

Treap树

Treap是一个合成词，由tree和Heap合成，可以翻译成树堆每一个结点有一个键值还有一个被称为优先级的权值，对于键值来说这棵树是一个排序二叉树，对于优先级来说，这是一个堆，在这个棵树的任意子树上，根结点的优先级最大。

Treap树的插入

1.用朴素的插入方法把node按键值插入到合适的子树上
2.给node随机分配一个优先级，如果node的优先级违反了堆的性质，即它的优先级比父结点高。那么就让node往上走，替代父节点，最后得到一个新的Treap树。
在步骤二中的调整用到了一个技巧 旋转，包括左旋和右旋

左旋和右旋

右旋

左旋

旋转代码，son[0]是左儿子，son[1]是右儿子 
void rotate(Node * &o,int d){                //d=0,左旋转；d=1，右旋转
        Node *k=o->son[d^1];                //d^1与1-d等价
        o->son[d^1]=k->son[d];             //相当于途中的between E and S
        k->son[d]=o;                
        o=k;                                //返回新的根
}

Treap树的删除

如果待删除的结点是叶子结点，直接删除就好了。
如果待删除的结点有两个子结点，那么找到优先级最大的一个子结点，把x向相反的反向旋转，也就是把向树的下层调整，直到x被旋转到叶子结点，然后直接删除。
然后是题目 hdu4585
以下代码都来源于紫书 题目的意思是对一群人有一个等级和一个id，一开始有一个老大，老大的等级是最高的，然后后面每输入一个人，对他的等级进行排序，输出和他等级最接近的一个人的id，由于题目的n比较大，因此普通的排序不行。

做法一：使用map自动排序的特点。

#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int main(void){
    int n;
    while(~scanf("%d",&n)&&n){
        mp.clear();
        mp[1000000000]=1;     //老大的等级最高
        while(n--){
            int id,g;
            scanf("%d%d",&id,&g);
            mp[g]=id;
            int ans;
            map<int,int>::iterator it=mp.find(g);   //找到排序好的位置
            if(it==mp.begin())
                ans=(++it)->second;
            else{
                map<int,int>::iterator it2=it;  //找到等级最接近的两个人
                it2--;
                it++;
                if(g-it2->first<=it->first-g)  //比较哪一个更接近
                    ans=it2->second;
                else
                    ans=it->second;
            }
            printf("%d %d\n",id,ans);
        }
    }
    return 0;
}

做法二：利用Treap树，等级就是结点的优先级

#include<bits/stdc++.h>
using namespace std;
int id[5000005];
struct Node{
    int size;                      //以这个结点为根的子树的结点总数量，用于名次数
    int rank;                       //优先级
    int key;                       //键值
    Node *son[2];
    bool operator < (const Node &a)const{return rank<a.rank;}   
    int cmp(int x)const{                           //内置函数 判断x和key的大小
        if(x==key) return -1;
        return x<key?0:1;
    }
    void update(){                                //更新size
        size=1;
        if(son[0]!=NULL)size+=son[0]->size;
        if(son[1]!=NULL)size+=son[1]->size;
    }
};
void rotate(Node * &o,int d){          //d=0左旋，d=1右旋
    Node *k=o->son[d^1];
    o->son[d^1]=k->son[d];
    k->son[d]=o;
    o->update();
    k->update();
    o=k;
}
void insert(Node * &o,int x){            //把x插到树中
    if(o==NULL){            
        o=new Node();
        o->son[0]=o->son[1]=NULL;
        o->rank=rand();
        o->key=x;
        o->size=1;
    }
    else{
        int d=o->cmp(x);           //Treap树是在BST的基础上 所以同样要满足根的左子叶更小 右子叶更大
        insert(o->son[d],x);           
        o->update();               //更新size
        if(o<o->son[d])             //如果子叶优先级大于父亲结点 则向相反的反向旋转 
            rotate(o,d^1);
    }
}
int kth(Node *o,int k){      //查找第k大的数   后面解释这个函数是怎么运作的
    if(o==NULL||k<=0||k>o->size)          
        return -1;
    int s=o->son[1]==NULL?0:o->son[1]->size;   
    if(k==s+1) return o->key;  
    else if(k<=s) return kth(o->son[1],k);
    else return kth(o->son[0],k-s-1);
}
int find(Node * o,int k){
    if(o==NULL)
        return -1;
    int d=o->cmp(k);
    if(d==-1)
        return o->son[1]==NULL?1:o->son[1]->size+1;
    else if(d==1)return find(o->son[d],k);
    else{
        int tmp=find(o->son[d],k);
        if(tmp==-1)return -1;
        else
            return o->son[1]==NULL?tmp+1:tmp+1+o->son[1]->size;
    }
}
int main(void){
    int n;
    while(~scanf("%d",&n)&&n){
        srand(time(NULL));
        int k,g;
        scanf("%d%d",&k,&g);
        Node * root=new Node();
        root->son[0]=root->son[1]=NULL;
        root->rank=rand();
        root->key=g;
        root->size=1;
        id[g]=k;
        printf("%d %d\n",k,1);
        for(int i=2;i<=n;++i){
            scanf("%d%d",&k,&g);
            id[g]=k;
            insert(root,g);
            int t=find(root,g);
            int ans1,ans2,ans;
            ans1=kth(root,t-1);
            ans2=kth(root,t+1);
            if(ans1!=-1&&ans2!=-1)
                ans=ans1-g>=g-ans2?ans2:ans1;
            else if(ans1==-1)ans=ans2;
            else ans=ans1;
            printf("%d %d\n",k,id[ans]);
        }
    }
    return 0;
}

关于kth函数的解释：
图片说明