伸展树(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;
}