代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MAXN = 20005;
const kk INF = 1ll<<61;
ll size[MAXN],val[MAXN],ch[MAXN][2];
ll n,root,tot,top;

inline void pushup(ll x)
{
	if(!ch[x][0]) return;
	size[x]=size[ch[x][0]]+size[ch[x][1]];
	val[x]=val[ch[x][1]];
}

inline ll newnode(ll k)
{return val[++tot]=k,size[tot]=1,tot;}

inline void rotate(ll x,ll k)
{
	ll w=ch[x][k],p=ch[x][k]=ch[x][k^1];
	ch[x][k^1]=ch[p][k^1],ch[p][k^1]=ch[p][k];
	ch[p][k]=w; pushup(ch[x][0]); pushup(ch[x][1]);
}

inline void maintain(ll x)
{
	if(!ch[x][0]) return;
	if(size[ch[x][0]]>=size[ch[x][1]]*2) rotate(x,1);
	if(size[ch[x][1]]>=size[ch[x][0]]*2) rotate(x,0);
}

void insert(ll x,ll k)
{
	if(!ch[x][0])
	{
		ch[x][0]=newnode(min(val[x],k));
		ch[x][1]=newnode(max(val[x],k));
		return pushup(x),void();
	}
	insert(ch[x][k>val[ch[x][0]]],k);
	pushup(x); maintain(x);
}

void dfs(ll x)
{
	if(ch[x][0]) dfs(ch[x][0]);
	if(!ch[x][0]&&val[x]^INF) a[top++]=val[x];
	if(ch[x][1]) dfs(ch[x][1]);
}

void sort(unsigned *a, ll n)
{
	n=read(); root=newnode(INF);
	for(ll i=0; i<n; ++i) insert(root,a[i]);
	dfs(root);
}

评测结果