唉，这大年初一的，刚看完春晚想敲一遍splay模板然后1A睡觉，然而晚上了各种傻逼各种错。。。一下子搞了两个多小时，简直醉了。。。
先是发现无故超时，然后凭借肉眼看出来splay函数中的==写成了=，无奈了。。。改了，交 麻痹还TLE，再看，又发现splay中 if(s==0) 写成 if(x==0) ，唉，权当打错啦，再改，交! 艹又是TLE。。。此时已过去俩小时。。。不慌，找！然后我就一个函数一个函数地排查调试，，，40min后，发现居然是在insert里吧lc[p]写成了lc[x]。。。再交，500msAC，，，好吧是我太粗心了，以后还是写一个函数调一个吧，在十几个函数里挑错误太累了。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 using namespace std; 9 const int maxn=200000; 10 int key[maxn],lc[maxn],rc[maxn],fa[maxn],siz[maxn]; 11 int tot,root; 12 int T; 13 void update(int x){ 14 siz[x]=siz[lc[x]]+1+siz[rc[x]]; 15 } 16 void r_rotate(int x){ 17 int y=fa[x]; 18 lc[y]=rc[x]; fa[rc[x]]=y; fa[x]=fa[y]; 19 if(y==lc[fa[y]]) lc[fa[y]]=x; 20 else rc[fa[y]]=x; 21 fa[y]=x; rc[x]=y; 22 update(x); update(y); 23 } 24 void l_rotate(int x){ 25 int y=fa[x]; 26 rc[y]=lc[x]; fa[lc[x]]=y; fa[x]=fa[y]; 27 if(y==lc[fa[y]]) lc[fa[y]]=x; 28 else rc[fa[y]]=x; 29 fa[y]=x; lc[x]=y; 30 update(x); update(y); 31 } 32 void splay(int x,int s){ 33 int p; 34 while(fa[x]!=s){ 35 p=fa[x]; 36 if(fa[p]==s){ 37 if(x==lc[p]) r_rotate(x); 38 else l_rotate(x); 39 break; 40 } 41 if(x==lc[p]){ 42 if(p==lc[fa[p]]) r_rotate(p),r_rotate(x); 43 else r_rotate(x),l_rotate(x); 44 } 45 else{ 46 if(p==rc[fa[p]]) l_rotate(p),l_rotate(x); 47 else l_rotate(x),r_rotate(x); 48 } 49 } 50 if(s==0) root=x; 51 update(x); 52 } 53 int find(int v){//查找在这棵树中键值为v的节点 54 int x=root; 55 while(x!=0){ 56 if(v<key[x]) x=lc[x]; 57 else if(v>key[x]) x=rc[x]; 58 else if(v==key[x]){ 59 splay(x,0); 60 return x; 61 } 62 } 63 return -1; 64 } 65 void New_node(int &x,int fath,int v){//建立新节点 66 x=++tot; 67 lc[x]=rc[x]=0; siz[x]=1; 68 fa[x]=fath; 69 key[x]=v; 70 } 71 void insert(int v){//插入新节点 72 if(root==0){ 73 New_node(root,0,v); 74 return ; 75 } 76 int p,x=root; 77 while(x!=0){ 78 p=x; 79 if(v<=key[x]) siz[x]++,x=lc[x]; 80 else siz[x]++,x=rc[x]; 81 } 82 if(v<=key[p]) New_node(lc[p],p,v); 83 else New_node(rc[p],p,v); 84 splay(tot,0); 85 } 86 int getmax(int x){//找到以x为根的最大值 87 while(rc[x]!=0) x=rc[x]; 88 return x; 89 } 90 int getmin(int x){//找到以x为根的最小值 91 while(lc[x]!=0) x=lc[x]; 92 return x; 93 } 94 int getpre(int x){//找到节点x的前驱 95 splay(x,0); 96 return getmax(lc[x]); 97 } 98 int getne(int x){//找到节点x的后继 99 splay(x,0); 100 return getmin(rc[x]); 101 } 102 void Delete(int v){//删除一个键值为v的节点 103 int x=find(v); 104 splay(x,0); 105 int pp=getpre(x),nn=getne(x); 106 splay(pp,0); 107 splay(nn,root); 108 int y=fa[x]; 109 fa[x]=0; 110 if(x==lc[y]) lc[y]=0; 111 else lc[x]=0; 112 update(x); update(y); 113 } 114 int rank(int rt,int v){//返回键值为v的节点的排名 115 if(rt==0) return 1; 116 if(v<=key[rt]) return rank(lc[rt],v); 117 else return siz[lc[rt]]+1+rank(rc[rt],v); 118 } 119 int findkth(int x,int k){//在以x为根的树中找第 k大 120 if(siz[lc[x]]+1==k) return key[x]; 121 if(siz[lc[x]]+1>k) return findkth(lc[x],k); 122 return findkth(rc[x],k-siz[lc[x]]-1); 123 } 124 125 int pred(int rt,int v){//返回比 v小的最大的数 126 if(rt==0) return v; 127 if(v<=key[rt]) return pred(lc[rt],v); 128 else{ 129 int ans=pred(rc[rt],v); 130 if(ans==v) return key[rt]; 131 return ans; 132 } 133 } 134 int succ(int rt,int v){//返回比 v大的最小的数 135 if(rt==0) return v; 136 if(v>=key[rt]) return succ(rc[rt],v); 137 else{ 138 int ans=succ(lc[rt],v); 139 if(ans==v) return key[rt]; 140 return ans; 141 } 142 } 143 int main(){ 144 scanf("%d",&T); 145 insert(-50000000); insert(50000000); 146 while (T--){ 147 int kin,num; 148 scanf("%d%d",&kin,&num); 149 if(kin==1) insert(num);//插入 150 else if(kin==2) Delete(num);//删除(若有多个相同的数，只删除一个) 151 else if(kin==3) printf("%d\n",rank(root,num)-1);//查询num数的排名(若有多个相同的数，因输出最小的排名) 152 else if (kin==4) printf("%d\n",findkth(root,num+1));//查询排名为x的数 153 else if (kin==5) printf("%d\n",pred(root,num)); 154 else if (kin==6) printf("%d\n",succ(root,num)); 155 } 156 return 0; 157 }
原文：http://www.cnblogs.com/CXCXCXC/p/5184877.html