记录编号	90579	评测结果	EEEEETTTTT
题目名称	排序测试	最终得分	0
用户昵称	请叫我“读者”	是否通过	未通过
代码语言	C++	运行时间	6.399 s
提交时间	2014-03-08 13:36:18	内存使用	0.31 MiB

#include <cstdio>
#include <iostream>
using namespace std;

template<typename T>
class SplayTree
{
public:
SplayTree();
    ~SplayTree();

    void del(const T &x);
    void insert(const T &x);
const T & min()
    {
        Node * p = root;
        while(p->lch != nullnode)
            p = p->lch;
        splay(root,p->key);
        return p->key;
    }
const T & max()
    {
        Node * p = root;
        while(p->rch != nullnode)
            p = p->rch;
        splay(root,p->key);
        return p->key;
    }
private:
struct Node
    {
        T key;
        Node *lch,* rch;
        Node(){}
        Node(const T & x) : key(x){}
    }* nullnode,* root;
    void left_rotate(Node * & x);
    void right_rotate(Node * & x);
    void splay(Node * &root,const T & x);
};
SplayTree<int>st;
template<typename T>
SplayTree<T>::SplayTree()
{
nullnode = new Node;
nullnode->lch = nullnode;
nullnode->rch = nullnode;
    root = nullnode;
}
template<typename T>
SplayTree<T>::~SplayTree()
{
    while(root != nullnode)
        del(max());
    delete nullnode;
}
template<typename T>
void SplayTree<T>::del(const T & x)
{
    Node * newroot;
    splay(root,x);
    if(x != root->key)
        return;         // No found...

    if(root->lch == nullnode)
newroot = root->rch;
    else
    {
newroot = root->rch;
        splay(newroot,x);
newroot->rch = root->rch;
    }
    delete root;
    root = newroot;
}
template<typename T>
void SplayTree<T>::insert(const T & x)
{
    Node * newroot = new Node(x);
    if(root == NULL)
    {
newroot->lch = nullnode;
newroot->rch = nullnode;
        root = newroot;
        return;
    }
    splay(root,x);
    if(x < root->key)
    {
newroot->lch = root->lch;
        root->lch = nullnode;
newroot->rch = root;
        root = newroot;
    }
    else
    {
newroot->rch = root->rch;
        root->rch = nullnode;
newroot->lch = root;
        root = newroot;
    }
}

template <typename T>
void SplayTree<T>::left_rotate(Node * & x)
{
    Node * y = x->rch;
    x->rch = y->lch;
    y->lch = x;
    x = y;
}

template <typename T>
void SplayTree<T>::right_rotate(Node * & x)
{
    Node * y = x->lch;
    x->lch = y->rch;
    y->rch = x;
    x = y;
}

template <typename T>
void SplayTree<T>::splay(Node * &root,const T & x)
{
    Node head,*ltree = & head,*rtree = & head;
head.lch = nullnode;
head.rch = nullnode;
    while(x != root->key)
    {
        if(x < root->key)
        {
            if(root->lch != nullnode&& x < root->lch->key)
right_rotate(root);
            if(root->lch == nullnode)
                break;
rtree->lch = root;
rtree = root;
            root = root->lch;
        }
        else
        {
            if(root->rch != nullnode&& x > root->rch->key)
left_rotate(root);
            if(root->rch == nullnode)
                break;
ltree->rch = root;
ltree = root;
            root = root->rch;
        }
    }
ltree->rch = root->lch;
    root->lch = head.rch;
rtree->lch = root->rch;
    root->rch = head.lch;
}

int main()
{
	int x,n,i;
	freopen("sorttest.in","r",stdin);
	freopen("sorttest.out","w",stdout);
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>x;
		st.insert(x);
	}
	for(i=0;i<n;i++)
	{
		x=st.min();
		cout<<x<<endl;
		st.del(x);
	}
    return 0;
}