记录编号	337713	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]统计数字	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.473 s
提交时间	2016-11-04 19:48:12	内存使用	0.26 MiB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _AVL
{
    int height;
    int data;
    int times;
    struct _AVL *left, *right;
}node, AVLNode, *AVLTree, *pNode;
#define HEIGHT(d) ((d)?(d)->height:-1)
inline int max(int a, int b){return a<b?b:a;}
void pushup(pNode k)
{
    k -> height = max(HEIGHT(k->left), HEIGHT(k->right))+1;
}
node *LLRotate(pNode k)
{
    pNode t = k->left;
    k->left = t->right;
    t->right = k;
    pushup(k);
    pushup(t);
    return t;
}
node *RRRotate(pNode k)
{
    pNode t = k->right;
    k->right = t->left;
    t->left = k;
    pushup(k);
    pushup(t);
    return t;
}
node *LRRotate(pNode k)
{
    k->left = RRRotate(k->left);
    return LLRotate(k);
}
node *RLRotate(pNode k)
{
    k->right = LLRotate(k->right);
    return RRRotate(k);
}
pNode insert(pNode t, int x)
{
    if(!t)
    {
        t = (pNode)malloc(sizeof(AVLNode));
        memset(t, 0, sizeof(AVLNode));
        t -> times = 1;
        t -> data = x;
    }else
    {
        if(x < t->data)
        {
            t->left = insert(t->left, x);
            if(HEIGHT(t->left) - HEIGHT(t->right) == 2)
            {
                if(x < t->left->data)
                    t = LLRotate(t);
                else
                    t = LRRotate(t);
            }
        }else if(x > t->data)
        {
            t->right = insert(t->right, x);
            if(HEIGHT(t->right) - HEIGHT(t->left) == 2)
            {
                if(x > t->right->data)
                    t = RRRotate(t);
                else
                    t = RLRotate(t);
            }
        }else
        {
            t->times++;
        }
    }
    pushup(t);
    return t;
}
void dfs(node *u)
{
    if(!u)return;
    dfs(u->left);
    printf("%d %d\n", u->data, u->times);
    dfs(u->right);
}
int main()
{
    freopen("pcount.in", "r", stdin);
    freopen("pcount.out", "w", stdout);
    int n;
    scanf("%d", &n);
    AVLTree t = NULL;
    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        t = insert(t, x);
    }
    dfs(t);
    return 0;
}