分类： 数据结构

我们将一棵以\(Splay\)方式维护的二叉搜索树封装为一个对象。
对于这个对象，我们定义它的一类私有对象\(Node\)，代表二叉搜索树上的一个节点。
对于这个节点，在通常情况下，我们需要维护的信息包括：
\(sn\)，这是一个有两个元素的数组。其中第\(0\)项表示左子节点，第\(1\)表示右子节点。
\(fa\)，表示它的父节点。
\(v\)，表示它的值。
\(nm\)，表示值为\(v\)的数的个数。
\(sz\)，表示所有子节点中的数的个数的和。

对于一棵二叉搜索树上的一个节点，我们定义它的旋转、单旋和双旋操作。
定义一个函数\(fndD(X)\)，表示一个节点相对于它的父节点是\(fndD(X)\)子节点
那么，一个节点\(X\)的旋转操作为：
将它的\(fndD(X)\ xor\ 1\)子节点作为它的父节点的\(fndD(X)\)子节点，并将\(X\)作为它的祖父节点的\(fndD(X_fa)\)节点，然后将它原来的父节点变成它的\(fndD(X)\ xor \ 1\)节点。
定义一个节点的单旋操作为，将这个节点向上旋转两次。
定义一个节点的双旋操作为，将这个节点的父节点向上旋转一次，然后再将这个节点向上旋转一次。
同时，我们定义一个将一个节点一直依据下述方法单旋/双旋到根的操作为一个伸展操作：
对于一个相对于其父亲的位置与其父亲相对于其祖父的位置相同的节点，对它采用双旋操作。
对于一个相对于其父亲的位置与其父亲相对于其祖父的位置不同的节点，对它采用单旋操作。

---

下面我们用一种被称为势能分析法的复杂度分析方式来分析它的复杂度。

我们定义关于一个节点\(X\)的势能函数\(\phi(X)\)，定义为它的子树大小取对数。我们定义关于整棵二叉搜索树\(T\)的一个势能函数\(\Phi (T)\)，定义为它的所有节点的\(\phi\)值之和。

对于第\(i\)次操作，我们定义一个函数\(T\)和一个摊还代价辅助函数\(A\)，其中\(T(i)\)表示第\(i\)次操作消耗的实际时间。\(A(i)\)由下述式子定义：
$$A_{i}=T_{i}+\Phi_{i}-\Phi_{i-1}$$
那么，我们可以得到公式：
$$A_{sum}=\sum_{i=1}^{q}A_{i}=\sum_{i=1}^{q}T_{i}+\Phi_{q}-\Phi_{0}$$
故而，我们只需要求出对于每一次操作的\(T\)与\(\Delta\Phi\)即可。

考虑到，每一个操作事实上都可以视为一次\(Splay\)操作，所以我们只需要考虑各类\(Splay\)操作造成的影响即可。
故而，我们需要计算的便是旋转、单旋和双旋对的操作复杂度以及它们对\(\Phi(T)\)的影响。

首先我们分析旋转操作。
容易知道，对于一次关于节点\(X\)的旋转操作，会改变\(\phi\)值的有且仅有两个节点：\(X\)和它的父亲\(Y\)。
我们定义\(X\)旋转后的节点为\(X’\)，\(Y\)旋转后的节点为\(Y’\)，很容易可以得到一个式子：
$$\Delta\Phi = \phi_{X’} – \phi_{X} + \phi_{Y’} – \phi_{Y}$$
考虑到旋转操作后，\(X’\)位于\(Y\)的位置，并且节点的数量没有增减、对父节点也没有影响，所以得到\(\phi_{X’}=\phi_{Y}\)
考虑\(Y’\)是\(X’\)的子节点，我们可以得到
$$ \phi_{X’} > \phi_{Y’}$$
将上述两式代入式中，可得：
$$\Delta\Phi < \phi_{X’} – \phi_{X}$$
于是可以证明，一次旋转的均摊复杂度上界是\(O(\phi_{X’}-\phi_{X})\)

然后我们分析单旋操作。
依然是定义一个关于节点\(X\)的旋转操作，定义它的父亲为\(Y\)，祖父为\(Z\)，旋转后分别为\(X’,Y’,Z’\)
很容易可以得到一个式子：
$$\Delta\Phi = \phi_{X’} – \phi_{X} + \phi_{Y’} – \phi_{Y} + \phi_{Z’} – \phi_{Z}$$
同理于旋转操作，我们可以得到：
$$\phi_{X’} = \phi_{Z}$$
故而：
$$\Delta\Phi = – \phi_{X} + \phi_{Y’} – \phi_{Y} + \phi_{Z’}$$
同理于旋转操作，我们可以得到：
$$\phi_{Y’}<\phi_{X’},\phi_{X}<\phi_{Y}$$ 故而：$$\Delta\Phi < \phi_{X’} + \phi_{Z’} – 2\phi_{X}$$$$\Delta\Phi < 2(\phi_{X’}-\phi_{X}) – \phi_{X’} – \phi_{Z’}$$又，$$\phi_{X’} + \phi_{Z’} = log_{2}{|X’||Z’|} > 2$$
所以，
$$\Delta\Phi < 2(\phi_{X’}-\phi_{X}) – 2$$

故而单旋操作的复杂度为\(O(\phi_{X’}-\phi_{X})\)

双旋操作的复杂度同理。

令总共进行了\(n\)次旋转操作，对于总体的复杂度上界，我们有：
$$A_{sum}<\sum_{i=1}^{n}\phi_{i}-\phi_{i-1}$$
故而得到最终的摊还复杂度：\(O(\phi_{n})\)

---

然而，上述的势能分析法仍然不够直观。下面我们考虑一种基于伸展操作的性质的另一种分析法。
引理一： 每一次伸展操作，必然会使得从这个节点到根的一条链的长度折半。
首先我们考虑单旋和双旋操作的使用情况。
我们称应当使用双旋的情况为一字型，应当使用单旋的情况为之字形，很容易可以发现，原来已有的一条链总是会被拆成两个部分。
而，详细地考虑各种情况，我们发现，不存在一种链，使得这种折半失效。
故而，我们得到了引理一。

下面考虑引理一是怎样在实际情况中发挥作用的。
我们说一个节点的深度可接受，指的是它的深度是\(log_2n\)的常数倍。
考虑对某一个节点进行操作。如果这个节点的深度可接受，那么操作它的复杂度也是可接受的。
如果这个节点的深度不可接受，根据引理一，总是可以在\(log_2n\)次操作以内将其的深度变为可接受的。
而每一次操作最多只会令这个链的深度加一，因此\(log_2n\)次操作的复杂度可以均摊到那些令这个链深度加一的操作上，从而使操作的均摊浮渣度仍然是可接受的。

注意：
1.三目运算符优先级比逗号高。
2.函数名不要搞混。
3.注意区分节点大小和子树大小。
4.当寻找前驱的时候，当前值与当前点的值相等应当向左走；当寻找后继时，当前值与当前点的值相等应当向右走。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXQ 1000005
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Min(int A,int B){
    return A<B?A:B;
}
class Splay{
	private:
		class Node{
    		public:
    			int sn[2];
    			int fa;
    			int v;
    			int nm;
    			int sz;
    			inline void set(int FA,int LS,int RS,int V){
    			    fa=FA,v=V,sn[0]=LS,sn[1]=RS,nm=1,sz=1;
                }
                inline void init(){
                	sn[0]=sn[1]=fa=v=nm=sz=0;
				}
		};
		int INF;
		Node tr[MAXQ];
		int st[100005],tp,cnt,rt;
		inline int fndD(int X){
			return tr[tr[X].fa].sn[0]==X?0:1;
		}
		inline void szRnw(int X){
		    tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].nm;
        }
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[tr[X].sn[D^1]].fa=tr[X].fa;tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa;tr[X].fa=tr[tr[X].sn[D^1]].fa;
			tr[tr[X].sn[D^1]].fa=X;tr[tr[X].fa].sn[D2]=X;
			szRnw(tr[X].sn[D^1]);szRnw(X);
			if(!tr[X].fa){
				rt=X;
			}
		}
		inline void splayTwo(int X){
		    int D=fndD(X),D2=fndD(tr[X].fa);
		    tr[X].fa?
				(tr[tr[X].fa].fa?
					(D==D2?
						(splayOne(tr[X].fa),splayOne(X),0)
						:(splayOne(X),splayOne(X),0))
					:(splayOne(X),0))
				:0;
		}
		inline void splayRnw(int X){
			while(tr[X].fa){
			    splayTwo(X);
            }
		}
		inline int nwlc(int FA,int LS,int RS,int V,int D){
			if(!cnt){
				rt=1;
			}
			int P=tp?st[tp--]:++cnt;
		    tr[FA].sn[D]=P;
		    tr[P].set(FA,LS,RS,V);
		    return P;
        }
        inline int fnd(int V){
            int P=rt,FP=0;
            while(P){
                FP=P;
                if(tr[P].v==V){
                    splayRnw(P);
                    return P;
                }
                P=tr[P].sn[tr[P].v>V?0:1];
            }
            return FP;
        }
        inline int fndMn(int X){
            int P=X,FP=tr[X].fa;
            while(P){
                FP=P;
                P=tr[P].sn[0];
            }
            return FP;
        }
        inline int fndMx(int X){
        	int P=X,FP=tr[X].fa;
        	while(P){
        		FP=P;
        		P=tr[P].sn[1];
			}
			return FP;
		}
		inline void clr(int X,int D){
			if(D==2){
				tr[X].init();
				st[++tp]=X;
				return;
			}
			rt=tr[X].sn[D],tr[tr[X].sn[D]].fa=0;
			tr[X].init();
			st[++tp]=X;
		}
		inline void init(int P){
			if(!tr[P].sn[0]||!tr[P].sn[1]){
				tr[P].sn[0]?(clr(P,0)):(tr[P].sn[1]?clr(P,1):clr(P,2));
			}else{
				int RS=fndMn(tr[P].sn[1]);
				tr[RS].sn[0]=tr[P].sn[0],tr[tr[P].sn[0]].fa=RS;
				clr(P,1);
				splayRnw(RS);
			}
			if(!tr[rt].v&&!tr[rt].sz&&!tr[rt].fa&&!tr[rt].nm){
				splayInit();
			}
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].sn[0]);
			printf("(%d)%d:[%d,%d][%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].fa);
			prnt(tr[X].sn[1]);
		}
	public:
	    inline void psh(int V){
	        int P=rt,FP=0,D=0;
	        while(P){
	            FP=P;
	            if(tr[P].v==V){
	                ++tr[P].nm;
	                splayRnw(P);
	                return;
                }
                D=tr[P].v>V?0:1;
	            P=tr[P].sn[tr[P].v>V?0:1];
            }
            splayRnw(nwlc(FP,0,0,V,D));
        }
        inline void del(int V){
            int P=fnd(V);
            splayRnw(P);
            tr[P].nm>1?(--tr[P].nm):(init(P),0);
        }
        inline int fndPre(int V){
            int P=rt,RT=-INF;
            while(P){
                RT=tr[P].v<V?Max(RT,tr[P].v):RT;
                P=tr[P].sn[tr[P].v<V?1:0];
            }
            return RT;
        }
        inline int fndNxt(int V){
            int P=rt,RT=INF;
            while(P){
                RT=tr[P].v>V?Min(RT,tr[P].v):RT;
                P=tr[P].sn[tr[P].v>V?0:1];
            }
            return RT;
        }
        inline int rnk(int V){
            int P=rt,RT=0;
            while(P){
                if(tr[P].v>V){
                    P=tr[P].sn[0];
                }else if(tr[P].v==V){
                    RT+=tr[tr[P].sn[0]].sz;
                    splayRnw(P);
                    return RT+1;
                }else{
                    RT+=tr[tr[P].sn[0]].sz+tr[P].nm;
                    P=tr[P].sn[1]; 
                }
            }
            return RT+1;
        }
        inline int aRnk(int V){
            int P=rt;
            while(P){
                if(tr[tr[P].sn[0]].sz+tr[P].nm<V){
                    V-=(tr[tr[P].sn[0]].sz+tr[P].nm);
                    P=tr[P].sn[1];
                }else if(tr[tr[P].sn[0]].sz<V){
                    return tr[P].v;
                }else{
                    P=tr[P].sn[0];
                }
            }
            return P;
        }
        inline void splayInit(){
			INF=2147483647,tp=0,cnt=0,rt=0;
			memset(tr,0,sizeof(tr));
		}
		inline void splayPrnt(){
			prnt(rt);
			puts("");
		}
}; 
Splay T;
void init(){
	int n,x,op;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		//T.splayPrnt();
		scanf("%d%d",&op,&x);
		switch(op){
			case 1:{
				T.psh(x);
				break;
			}
			case 2:{
				T.del(x);
				break;
			}
			case 3:{
				printf("%d\n",T.rnk(x));
				break;
			}
			case 4:{
				printf("%d\n",T.aRnk(x));
				break;
			}
			case 5:{
				printf("%d\n",T.fndPre(x));
				break;
			}
			case 6:{
				printf("%d\n",T.fndNxt(x));
				break;
			}
		}
	}
}
int main(){
//	freopen("Splay.out","w",stdout);
	T.splayInit();
	init();
	return 0;
}