写一种数据结构，来维护一些数，其中需要提供以下操作：
- 插入x数
- 删除x数(若有多个相同的数，应只删除一个)
- 查询x数的排名(若有多个相同的数，应输出最小的排名)
- 查询排名为x的数
- 求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
这就是伸展树的基本操作，也是伸展树名字的由来（这里讲算法不讲历史）。
重要的的函数有Rotate，Splay和Del其他的都是一些树上操作罢了。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
#include<set> #include<map> #include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define qread(x) x=read() #define mes(x,y) memset(x,y,sizeof(x)) #define Maxn 100000 #define INF 2147483647 inline int read(){ int f=1,x=0;char ch=getchar(); while(!(ch>='0'&&ch<='9')){if(ch=='-')f*=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } struct Splaytree{ int d,c,n,f,son[2]; //d为当前节点的值,c以此节点为根的子树有多少个数，n为这个点有多少数,f它的父亲节点,son左孩子右孩子 }Tr[Maxn+1];int len,root; void update(int x){ Tr[x].c=Tr[Tr[x].son[0]].c+Tr[Tr[x].son[1]].c+Tr[x].n; //计算以x点为跟的子树有多少个数 } void rotate(int x,int w){ //x为当前旋转的点，w为旋转后父亲是x的左孩子（左旋）还是右孩子（右旋） int f=Tr[x].f,ff=Tr[f].f; int r,R; //r认R为父亲 r=Tr[x].son[w];R=f; Tr[R].son[1-w]=r; if(r!=0)Tr[r].f=R; //我的w孩子变成父亲的1-w孩子,如果孩子存在，孩子认父亲 r=x;R=ff; if(Tr[R].son[0]==f)Tr[R].son[0]=r; else Tr[R].son[1]=r;//判断是左孩子还是右孩子更新 Tr[r].f=R; //我认我父亲的父亲为父亲 r=f;R=x; Tr[R].son[w]=r; Tr[r].f=R; //父亲变为我的w孩子 update(f); update(x); //更新前父亲和自己的节点个数 } void add(int d,int f){//认f为父亲 len++; Tr[len].d=d;Tr[len].n=1;Tr[len].c=1; Tr[len].f=f; //全部赋值参数 if(d<Tr[f].d)Tr[f].son[0]=len; else Tr[f].son[1]=len;//判断是左孩子还是右孩子，所以插入要插入在叶子节点 Tr[len].son[0]=Tr[len].son[1]=0; //两个孩子都没有 } void splay(int x,int rt){ while(Tr[x].f!=rt){//如果我现在的父亲不是rt int f=Tr[x].f,ff=Tr[f].f; if(ff==rt){//如果只要跳一步就可以使得rt是f，就只要我和父亲换位置 if(Tr[f].son[0]==x)rotate(x,1);//左孩子右旋，右孩子左旋 else rotate(x,0); } else{ if(Tr[ff].son[0]==f&&Tr[f].son[0]==x){rotate(f,1);rotate(x,1);}//其实也可以x右旋两次，只不过容易成链，所以要分开旋 else if(Tr[ff].son[1]==f&&Tr[f].son[1]==x){rotate(f,0);rotate(x,0);} else if(Tr[ff].son[0]==f&&Tr[f].son[1]==x){rotate(x,0);rotate(x,1);} else if(Tr[ff].son[1]==f&&Tr[f].son[0]==x){rotate(x,1);rotate(x,0);} //但是后两种情况选择f的话是不会改变x的位置，所以只能旋x } } if(rt==0)root=x;//如果为0记得改根 } int findip(int d){ int x=root;//从根节点开始找 while(Tr[x].d!=d){//如果是的话直接赶回 if(d<Tr[x].d){//不是的话向左或者向右找，知道找到没有的 if(Tr[x].son[0]==0)break; else x=Tr[x].son[0]; } else{ if(Tr[x].son[1]==0)break; else x=Tr[x].son[1]; } } return x; } void ins(int d){ if(root==0){ add(d,0); root=len; return; } //如果没有根，直接来 int x=findip(d);//找最接近x的点 if(Tr[x].d==d){ Tr[x].n++; update(x); splay(x,0);//找到一个人就转一下，避免成一条链 } //有的话那就n++就好，但是要更新，并且splay上来 else{ add(d,x);//如果没有的话就在这个点插入 update(x); splay(len,0); } } void del(int d){ int x=findip(d);splay(x,0);//已经旋到根了 if(Tr[x].n>1){Tr[x].n--;update(x);return;}//如果可以的话直接减，但是修改时记得update if(Tr[x].son[0]==0&&Tr[x].son[1]==0){root=0;len=0;}//根没有孩子，直接删点 else if(Tr[x].son[0]==0&&Tr[x].son[1]!=0){root=Tr[x].son[1];Tr[root].f=0;}//如果只有左，那就改根为左，左点认父亲0 else if(Tr[x].son[0]!=0&&Tr[x].son[1]==0){root=Tr[x].son[0];Tr[root].f=0;} else{ //如果都不是的话，把小于d的最大值旋上来 int p=Tr[x].son[0];while(Tr[p].son[1]!=0)p=Tr[p].son[1];splay(p,x);//转到x左边 int r=Tr[x].son[1],R=p; Tr[R].son[1]=r; Tr[r].f=R; root=R;Tr[root].f=0; update(R);//然后认父亲，认了就完了 } } int findpaiming(int d){ int x=findip(d);splay(x,0);//找到d，然后splay上来，找到左子树值+1 return Tr[Tr[x].son[0]].c+1; } int findshuzi(int k){ int x=root; while(1){ int lc=Tr[x].son[0],rc=Tr[x].son[1]; if(k<=Tr[lc].c)x=lc;//不够就去左边找 else if(k>Tr[lc].c+Tr[x].n){//够了就去右边找 k-=Tr[lc].c+Tr[x].n;//减去左边加自己的 x=rc; } else break;//找到了退出 } splay(x,0); return Tr[x].d; } int findqianqu(int d){ int x=findip(d);splay(x,0);//找到d，然后找左孩子的最右孩子 if(d<=Tr[x].d&&Tr[x].son[0]!=0){//怕找到的x时最接近的而已，所以要先判断一下 x=Tr[x].son[0]; while(Tr[x].son[1]!=0)x=Tr[x].son[1]; } if(d<=Tr[x].d)x=0;//如果找不到，x=0 return x; } int findhouji(int d){ int x=findip(d);splay(x,0);//同理找有孩子的最左孩子 if(Tr[x].d<=d&&Tr[x].son[1]!=0){ x=Tr[x].son[1]; while(Tr[x].son[0]!=0)x=Tr[x].son[0]; } if(Tr[x].d<=d)x=0; return x; } int n,opt,x; int main(){ qread(n); root=0;len=0; for(int i=1;i<=n;i++){ qread(opt),qread(x); if(opt==1)ins(x); else if(opt==2)del(x); else if(opt==3)printf("%dn",findpaiming(x)); else if(opt==4)printf("%dn",findshuzi(x)); else if(opt==5)printf("%dn",Tr[findqianqu(x)].d); else if(opt==6)printf("%dn",Tr[findhouji(x)].d); } //看着进行操作就对了,每访问到一个点必定要splay,没修改一个点必定要update } |
......