描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入x数

2. 删除x数(若有多个相同的数，因只删除一个)

3. 查询x数的排名(若有多个相同的数，因输出最小的排名)

4. 查询排名为x的数

5. 求x的前驱(前驱定义为小于x，且最大的数)

6. 求x的后继(后继定义为大于x，且最小的数)

输入

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

输出

对于操作3,4,5,6每行输出一个数，表示对应答案

样例输入[复制]

8 

1 10 

1 20 

1 30 

3 20 

4 2 

2 10 

5 25 

6 -1

样例输出[复制]

2 

20 

20 

20

提示

n<=100000 所有数字均在-10^7到10^7内

 

主要就是放个板子

板子treap：

1 #include
      
         2 using namespace std;  3 #define Mlen 1000000  4 #define INF 0x7fffffff  5 struct Node {  6     int f,val,m,siz;  7     //f是平衡因子，val是值，m是相同数个数，siz是该树节点数量  8     int chd[2];  9     Node(int val=0):val(val) { 10         f = rand()%100000;//给平衡因子赋值  11         chd[0]=chd[1]=0;//左儿子与右儿子均初始化为0  12         m=siz=1;//重复的数量和子树节点数量都是1  13     } 14 } T[Mlen]; 15 int n,root,last; 16 void update(int p) { //更新节点 17     T[p].siz = T[T[p].chd[0]].siz + T[T[p].chd[1]].siz+T[p].m;//这个点的子树数量就是左儿子的数量加上右儿子的数量再加上自己的个数  18 } 19 void ratate(int & p,int d) { //d=0右旋，d=1为左旋  20     int chd = T[p].chd[d];//（右旋作为例子）用chd临时保存这个节点的左儿子 21     T[p].chd[d] = T[chd].chd[d^1];//这个节点的左儿子更新为左儿子的右儿子  22     T[chd].chd[d^1]  = p;//这个节点的左儿子的右儿子就变成了这棵树的根节点  23     T[chd].siz = T[p].siz;//这个点 的节点数量就是p子树根的子节点数量  24     update(p);//维护原来的子树根新的子节点数量  25     p = chd;//这个节点的编号就变成了子树的编号  26 } 27 int insert(int &p,int x) {
    //插入函数  28     if(p==0) {
    //如果这个节点是叶节点  29         p=++last;//由于我们使用一维数组来存储节点，所以遇到空的叶节点时我们就新开一个节点作为上一次调用的儿子  30         T[p].val = x;// 这个节点的值就变为x  31         return 1;//返回一个类似bool 为真  32     } 33     if(T[p].val ==x) {
    //如果找到一个节点的值是当前传入的值  34         //T[p].siz++;    //如果要求不重复就返回0 35         T[p].m++;//这个节点所代表的相同的树就加上1  36         update(p);//对p进行维护  37         return 1;//返回类似一个bool值  38     } 39     /*简写 40          int d=x>T[p].val; 41          int &chd = T[p].chd[d]; 42         if(!insert(chd,x))return 0; 43         if(T[chd].f < T[p].f) ratate(p,d); 44     */ 45     if(x
       
        1) {
    //如果有重复的数字在一个点里面  63             T[p].siz--;// 这颗子树的节点数-1，  64             T[p].m--;//这个节点重复的数的个数也要-1 65             return 1;//返回真  66         } else { 67             if(T[p].chd[0]==0) {
    //如果这个节点的左儿子不存在  68                 p=T[p].chd[1];//那么这个节点编号就是这个节点的右儿子  69                 return 1;//返回真  70             } 71             if(T[p].chd[1]==0) {
    //如果这个节点的右儿子不存在 72                 p=T[p].chd[0];//那么这个节点的编号就是左儿子 ，跳过  73                 return 1;//返回真  74             } 75             if(T[p].chd[0]&&T[p].chd[1]) {
    //如果这两个儿子都不是0，意思是已经有定义  76                 if( T[T[p].chd[0]].f < T[T[p].chd[1]].f) {
    //如果这个节点的左儿子的平衡因子小于右儿子的平衡因子  77                     ratate(p,0);//进行右旋  78                     T[p].siz--;//这个子树的节点数量-1  79                     return del(T[p].chd[1],x);//同时进行递归删除新的根的右儿子  80                 } else { 81                     ratate(p,1);//如果不是，就进行左旋  82                     T[p].siz--;//这个子树的节点数量-1  83                     return del(T[p].chd[0],x);//再次进行递归操作删除新的根的左儿子  84                 } 85             } 86         } 87     } 88     if(!del(T[p].chd[x
        
         \n",p,T[p].val,T[p].siz,T[p].m,T[p].f); 96     zhong(T[p].chd[1]);//打印右边的顺序  97 } 98 void qian(int p) {
    //调试使用函数  99     if(!p) return ;100     printf("%d:val=%d,siz=%d,m=%d,f=%d->\n",p,T[p].val,T[p].siz,T[p].m,T[p].f);101     qian(T[p].chd[0]);102     qian(T[p].chd[1]);103 }104 int f_rank(int &p,int x) {
    //查询x的排名函数 105     if(p==0) return 0;//如果这个节点是空节点，那么就直接返回 106     int left_siz = T[T[p].chd[0]].siz; //静态数组的好处，左边的子树节点数量赋值给left_siz 107     if(x==T[p].val) return left_siz + 1;//如果我们所要查找的值是这个节点的值 ，那么就返回这个节点的左子树的节点数量+1（因为如果相同，由于这个点的左子树全部且只有这些比它小，所以就直接+1） 108     if(x < T[p].val)//如果是小于当前搜索的节点 ，那么就肯定在左边 109         return f_rank(T[p].chd[0],x);//返回左子树寻找到的值 110     else111         return f_rank(T[p].chd[1],x) + T[p].m + left_siz; //左支树节点数，+本节点重复数—+右支树排名112 }113 int f_num(int &p,int x) { //找第x名的数 114     if(!p) return 0;//如果搜寻到的是一个空的叶子节点，那么就搜索失败并且返回 ，并说明是0 115     int left_siz =T[T[p].chd[0]].siz;//左子树的节点数量赋值给left_siz 116     if(left_siz < x && x <= left_siz+T[p].m ) return T[p].val;//如果当前值是大于左子树所有节点的数量并且这个排名是小于当前序号的值加上这个点重复的个数，那么这个排名所对应的值肯定就是这个点 117     if(x <= left_siz) return f_num(T[p].chd[0],x);//如果左支树节点数更多或者等于（如果等于实际上就是左子树 的值）， 说明 这个值还在左子树里面 118     if(x > left_siz +T[p].m)  return f_num(T[p].chd[1],x - left_siz -T[p].m);//反过来，如果比这个点的左子树节点数量加上这个节点的重复数量的总和还要大，那么就肯定在右子树 119 }120 int f_pred(int &p,int x) {
    //求x的前驱的函数 121     if(!p)return -INF;//如果这个节点不存在，那么返回不存在 122     if( x<=T[p].val)return f_pred(T[p].chd[0],x);//如果x比当前节点要小，这个点的前驱那么就返回右边的值 123     int res;//使用一个临时变量 124     res=f_pred(T[p].chd[1],x);//当前节点可能是最大的，和右支树最大比较，右子树有可能有更接近的 125     return T[p].val > res?T[p].val:res;//126 }127 int f_succ(int &p,int x) { //找后续，的函数 128     if(!p)return INF;129     if(x>=T[p].val)//如果大于根节点，后续肯定在右支树130         return f_succ(T[p].chd[1],x);131     int res;132     res=f_succ(T[p].chd[0],x);//当前节点可能是最大的，和右支树最大比较133     return T[p].val < res?T[p].val:res;//相当于小于比较左支树和根节点大小134 }135 int main() {136     srand(unsigned(time(0)));137     scanf("%d",&n);138     root=0;139     last=0;140     T[0].siz=0;141     T[0].m=0;142     T[0].f=0;143     while(n--) {144         int q,x;145         scanf("%d%d",&q,&x);146         switch(q) {
    //输入操作编号 147             case 1:148                 insert(root,x);149                 break;150             case 2:151                 del(root,x);152                 break;153             case 3:154                 printf("%d\n",f_rank(root,x));155                 break;156             case 4:157                 printf("%d\n",f_num(root,x));158                 break;159             case 5:160                 printf("%d\n",f_pred(root,x));161                 break;162             case 6:163                 printf("%d\n",f_succ(root,x));164                 break;165         }166         //    printf("root=%d\n",root);167         //    for(int i=0;i<=10;i++)printf("siz=%d,m=%d,val=%d\n",T[i].siz,T[i].m,T[i].val);printf("\n");168     }169 //    qian(root);170 //    printf("%d\n",root);171 //    zhong(root);172 //173     return 0;174 }
        
       
      

 

 

splay：

//写splay，rotate操作写两个参数//保存原数使用k数组//统计该点个数用cnt数组//统计编号使用ind数组//统计子树大小使用siz数组//父亲使用fa数组，儿子用ch数组#include
      
       #include
       
        #define N 100006using namespace std;int root,tot,ind,m,n;int fa[N],ch[N][2],cnt[N],siz[N],k[N];void update(int x) {    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}int get(int x) {    return ch[fa[x]][1]==x;}void rotate(int x,int &t) {    int y=fa[x],z=fa[y],d=get(x),d1=get(y);    if(y==t)t=x;    else ch[z][d1]=x;    ch[y][d]=ch[x][d^1];    fa[ch[x][d^1]]=y;    ch[x][d^1]=y;    fa[y]=x;    fa[x]=z;    update(y);    update(x);}void splay(int x,int &t) {    for(int y=fa[x],z=fa[y]; x!=t; rotate(x,t),y=fa[x],z=fa[y])        if(y!=t)rotate(get(x)==get(y)?y:x,t);}int search(int v) {    int p=root;    while(p&&v!=k[p])p=ch[p][k[p]
        
         1) {        cnt[p]--;        siz[p]--;        return;    }    int l=ch[p][0],r=ch[p][1],lm;    lm=l;    fa[l]=fa[r]=ch[p][0]=ch[p][1]=0;    root=l;    while(lm&&ch[lm][1])lm=ch[lm][1];    if(!lm) {        root=r;        return;    }    splay(lm,root);    ch[lm][1]=r;    if(r)fa[r]=lm;    update(root);}int grank(int x) {    splay(x,root);    return siz[ch[x][0]]+1;}int kth(int o,int k) {    int lsiz=siz[ch[o][0]];//查询左子树的大小    if(k<=lsiz+cnt[o]&&k>=lsiz+1)return o;//如果左子树加上这个点的大小恰好等于查询的k，就直接返回根节点    if(lsiz>k-cnt[o])return kth(ch[o][0],k);//如果左边的点数量大于等于，就要调查左边的树，因为是要找第k名    return kth(ch[o][1],k-lsiz-cnt[o]);//如果左边不够，右边就来凑数 }void insert(int v) {    if(!root) {        root=++ind;        k[root]=v;        siz[root]=cnt[root]=1;        ch[root][0]=ch[root][1]=fa[root]=0;    } else if(search(v)) {        int t=search(v);        splay(t,root);        siz[t]++;        cnt[t]++;    } else {        int x=root,y;        for(;;) {            y=ch[x][k[x]