伸展樹(Splay)這個東西，轉來轉去的，真好玩。

今天第一次寫Splay，Splay操作太強大了。Splay(x,y)操作爲把節點x旋轉到y節點下面，均攤時間複雜度爲O(logN)。

有了這個東西，就能實現兩棵Splay合併，要求一棵比另一棵所有元素都小。合併兩棵伸展樹a,b(a<b)，方法爲把a中的最大值c，splay到a的根節點，此時a樹根節點的右子樹爲空，接下來把b樹接到c的右子樹就行了。

有了合併這個東西，Splay的刪除就比任何平衡樹的刪除都簡單了。方法就是先把要刪除的節點Splay到根位置，然後合併根節點的兩棵子樹即可（有點像左偏樹）。

Splay太好玩了，繼續研究。

NOIP2007 統計數字 Splay

/* 
 * Problem: NOIP2007 統計數字
 * Author: Guo Jiabao
 * Time: 2009.5.16 17:16
 * State: Solved
 * Memo: 伸展樹 Splay 插入 刪除 合併 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=200001;
using namespace std;
struct SplayTree
{
    struct ST_Node
    {
        ST_Node *left,*right,*father;
        int value,weight;
    }*root;
    int SC;
    ST_Node SE[MAXN];
    void ZIG(ST_Node *x)
    {
        ST_Node *y=x->father;
        // x->right
        y->left = x->right;
        if (x->right)
            x->right->father=y;
        // y->father
        x->father = y->father;
        if (y->father)
        {
            if (y==y->father->left)
                y->father->left = x;
            else
                y->father->right = x;
        }
        // y
        x->right = y;
        y->father = x;
    }
    void ZAG(ST_Node *x)
    {
        ST_Node *y=x->father;
        // x->left
        y->right = x->left;
        if (x->left)
            x->left->father=y;
        // y->father
        x->father = y->father;
        if (y->father)
        {
            if (y==y->father->left)
                y->father->left = x;
            else
                y->father->right = x;
        }
        // y
        x->left = y;
        y->father = x;
    }
    void Splay(ST_Node *x,ST_Node *y)
    {
        while (x->father != y)
        {
            if (x->father->father == y)
            {
                if (x->father->left == x)
                    ZIG(x);
                else
                    ZAG(x);
            }
            else if (x->father->father->left == x->father)
            {
                if (x->father->left == x)
                {
                    ZIG(x->father);
                    ZIG(x);
                }
                else
                {
                    ZAG(x);
                    ZIG(x);
                }
            }
            else
            {
                if (x->father->right == x)
                {
                    ZAG(x->father);
                    ZAG(x);
                }
                else
                {
                    ZIG(x);
                    ZAG(x);
                }
            }
        }
        if (y==0)
            root=x;
    }
    void insert(int value)
    {
        ST_Node **p=&root,*y=0;
        for (;;)
        {
            if (!*p)
            {
                *p=SE+ (++SC);
                (*p)->left = (*p)->right = 0;
                (*p)->value = value;
                (*p)->weight = 1;
                (*p)->father = y;
                Splay(*p,0);
                break;
            }
            y=*p;
            if (value == (*p)->value)
            {
                (*p)->weight ++;
                Splay(*p,0);
                break;
            }
            else if (value < (*p)->value)
                p=&(*p)->left;
            else
                p=&(*p)->right;
        }
    }
    ST_Node* join(ST_Node *a,ST_Node *b)
    {
        if (a) a->father=0;
        if (b) b->father=0;
        if (!b)    return a;
        if (!a) return b;
        ST_Node *c=a;
        for (;c->right;c=c->right);
        Splay(c,0);
        c->right=b;
        b->father=c;
        return c;
    }
    void remove(ST_Node *x)
    {
        Splay(x,0);
        root=join(x->left,x->right);
    }
    void delmin(int &min,int &cnt)
    {
        ST_Node *x=root;
        for (;x->left;x=x->left);
        min=x->value; cnt=x->weight;
        remove(x);
    }
}Splay;
int N;
int main()
{
    int i,c,v;
    freopen("pcount.in","r",stdin);
    freopen("pcount.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&c);
        Splay.insert(c);
    }
    while (Splay.root)
    {
        Splay.delmin(v,c);
        printf("%d %d\n",v,c);
    }
    return 0;
}