Splay tree 伸展樹 （不含區間操作）模闆

寫了三天的Splay終于AC了，題是用的學校題庫裡的平衡樹的題，由于剛接觸Splay，就用那個不含區間操作的練手，結果挂了三天。。這一定會成為黑曆史

題目如下：

2183: 普通平衡樹

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 269   Solved: 119

[ Submit][ Status][ Web Board]

Description

此為平衡樹系列第一道：普通平衡樹您需要寫一種資料結構（可參考題目标題），來維護一些數，其中需要提供以下操作：

1. 插入x數

2. 删除x數(若有多個相同的數，因隻删除一個)

3. 查詢x數的排名(若有多個相同的數，因輸出最小的排名)

4. 查詢排名為x的數

5. 求x的前驅(前驅定義為小于x，且最大的數)

6. 求x的後繼(後繼定義為大于x，且最小的數)

Input

第一行為n，表示操作的個數,下面n行每行有兩個數opt和x，opt表示操作的序号(1<=opt<=6)

Output

對于操作3,4,5,6每行輸出一個數，表示對應答案

Sample Input

8 1 10 1 20 1 30 3 20 4 2 2 10 5 25 6 -1

Sample Output

2 20 20 20

HINT

n<=100000 所有數字均在-107到107内

這個題用啥平衡樹都能過，我用Treap和SBT寫過，但是Splay要注意的小問題太多了，導緻自己一直挂着

比如說每個節點的father域和son域在更新的時候千萬不要忘記更新father域，我就是在這個問題上一直挂着，好孩子千萬不要像我學習啊！！

旋轉操作：

右旋操作：

右旋+左旋 \ 左旋+右旋

配合上面的圖檔了解動筆畫畫應該能很快了解Splay平衡的原理

代碼：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x7f7f7f7f
using namespace std;
 
struct Complex{
    int val,cnt,size;
    Complex *son[2],*father;
    void Maintain();
    int Compare(int x) {
        if(x == val)    return -1;
        return x > val;
    }
    bool Check() {
        return father->son[1] == this;
    }
}none,*nil = &none,*root = nil;
 
inline void Splay(Complex *x,Complex *aim);
inline void Rotate(Complex *x,bool dir);
inline void Insert(int x);
void Update(Complex *now);
inline Complex *NewNode(Complex *f,int val);
void Delete(Complex*& a,int x);
inline Complex *Find(int x);
int Find(Complex* a,int x);
int FindK(Complex *a,int k);
int FindPred(Complex *a,int x);
int FindSucc(Complex *a,int x);
 
int main()
{
    nil->son[0] = nil->son[1] = nil;
    nil->father = nil;
    nil->size = nil->cnt = 0;
    int cnt;
    cin >> cnt;
    for(int flag,x,i = 1;i <= cnt; ++i) {
        scanf("%d%d",&flag,&x);
        switch(flag) {
            case 1:Insert(x);break;
      		case 2:Delete(root,x);break;
            case 3:printf("%d\n",Find(root,x));break;
            case 4:printf("%d\n",FindK(root,x));break;
            case 5:printf("%d\n",FindPred(root,x));break;
            case 6:printf("%d\n",FindSucc(root,x));break;
        }
    }
    return 0;
} 
 
void Complex :: Maintain()
{  
    if(this == nil) return ;
    size = cnt + son[0]->size + son[1]->size;
}
 
inline void Splay(Complex *x,Complex *aim)
{
    while(x->father != aim) {
        if(x->father->father == aim) {
            if(!x->Check())  Rotate(x,true);
            else    Rotate(x,false);
        }
        else if(!x->father->Check()) {
            if(!x->Check()) {
                Rotate(x->father,true);
                Rotate(x,true);
            }
            else {
                Rotate(x,false);
                Rotate(x,true);
            }
        }
        else {
            if(x->Check()) {
                Rotate(x->father,false);
                Rotate(x,false);
            }
            else {
                Rotate(x,true);
                Rotate(x,false);
            }
        }
        x->Maintain();
    }
}
 
inline void Rotate(Complex *x,bool dir)
{
    Complex *f = x->father;
    f->son[!dir] = x->son[dir];
    f->son[!dir]->father = f;
    x->son[dir] = f;
    x->father = f->father;
    if(f->father->son[0] == f)
    	f->father->son[0] = x;
   	else	f->father->son[1] = x;
    f->father = x;
    f->Maintain(),x->Maintain();
    if(root == f)   root = x;
}
 
inline void Insert(int x)
{
    if(root == nil) {
        root = NewNode(nil,x);
        return ;
    }
    Complex *now = root;
    while(true) {
        int dir = now->Compare(x);
        if(dir == -1) {
            now->cnt++;
            Update(now);
            return ;
        }
        else if(now->son[dir] != nil)
            now = now->son[dir];
        else {
            now->son[dir] = NewNode(now,x);
            Update(now);
            Splay(now->son[dir],nil);
            return ;
        }
    }
}
 
void Update(Complex* now)
{
    now->Maintain();
    if(now != root)
        Update(now->father);
}
 
inline Complex *NewNode(Complex* f,int val)
{
    Complex *re = new Complex();
    re->cnt = re->size = 1;
    re->val = val;
    re->son[0] = re->son[1] = nil;
    re->father = f;
    return re;
}

void Delete(Complex*& a,int x)
{
	int dir = a->Compare(x);
	if(dir != -1)
		Delete(a->son[dir],x);
	else {
		if(a->cnt > 1)	a->cnt--;
		else {
			if(a->son[0] == nil) a->son[1]->father=a->father,	a = a->son[1];
			else if(a->son[1] == nil) a->son[0]->father=a->father,	a = a->son[0];
			else {
				Rotate(a->son[0],true);
				Delete(a->son[1],x);
			}
		}
	}
	if(a != nil)	a->Maintain();
}
 
inline Complex *Find(int x)
{
    Complex *now = root;
    while(true) {
        int dir = now->Compare(x);
        if(dir == -1)   return now;
        now = now->son[dir];
    }
}

int Find(Complex *a,int x)
{
	int re = a->son[0]->size;
	int dir = a->Compare(x);
	if(!dir)	return Find(a->son[0],x);
	if(dir == -1)	return re + 1;
	return re + a->cnt + Find(a->son[1],x);
}
 
int FindK(Complex *a,int k)
{
    int l = a->son[0]->size;
    if(k <= l)	return FindK(a->son[0],k);
    k -= l;
    if(k <= a->cnt)	return a->val;
    k -= a->cnt;
    return FindK(a->son[1],k);
}
 
int FindPred(Complex* a,int x)
{
	if(a == nil)	return -INF;
    if(x <= a->val)   return FindPred(a->son[0],x);
    return max(a->val,FindPred(a->son[1],x));
}
 
int FindSucc(Complex* a,int x)
{
	if(a == nil)	return INF;
    if(x >= a->val)   return FindSucc(a->son[1],x);
    return min(a->val,FindSucc(a->son[0],x));
}