http://poj.org/problem?id=3481

直接splay，WA...

#include<bits/stdc++.h>
#define PI acos(-1)
#define N 2001001
#define MAX 2001
#define re register
#define inf 1000000000000000000
using namespace std;
typedef double db;
typedef long long ll;
inline void read(re ll &ret)
{
    ret=0;re char c=getchar();re bool pd=false;
    while(!isdigit(c)){pd|=c=='-';c=getchar();}
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
    ret=pd?-ret:ret;
    return;
}
ll op,k,p,n,root;
struct node
{
	ll son[2],fa,val,p;
}a[N];
#define ls(t) a[t].son[0]
#define rs(t) a[t].son[1]
#define fa(t) a[t].fa
#define val(t) a[t].val
inline bool getson(re ll p,re ll q)
{
	return a[q].son[1]==p;
}
inline void connect(re ll p,re ll q,re bool son)
{
	fa(p)=q;
	a[q].son[son]=p;
	return;
}
inline void rotate(re ll ver)
{
	re ll g=fa(ver);
	re ll gg=fa(g);
	re bool g1=getson(ver,g),g2=getson(g,gg);
	connect(a[ver].son[!g1],g,g1);
	connect(g,ver,!g1);
	connect(ver,gg,g2);
	return;
}
inline void splay(re ll ver)
{
	while(fa(ver))
	{
		re ll g=fa(ver);
		if(fa(g))
		{
			if(getson(ver,g)==getson(g,fa(g)))
				rotate(g);
			else
				rotate(ver);
		}
		rotate(ver);
	}
	root=ver;
	return;
}
inline void destroy(re ll ver)
{
	a[ver].son[0]=a[ver].son[1]=fa(ver)=val(ver)=a[ver].p=0;
	if(n&&ver==n)
		n--;
	return;
}
inline void insert(re ll val,re ll p)
{
	if(!n)
	{
		n++;
		ls(n)=rs(n)=fa(n)=0;
		root=n;
		val(n)=val;
		a[n].p=p;
		return;
	}
	re ll now=root;
	while(true)
	{
		re ll ver=now;
		if(a[now].p<p)
		{
			now=rs(now);
			if(!now)
			{
				ls(++n)=rs(n)=fa(n)=0;
				fa(n)=ver;
				rs(ver)=n;
				val(n)=val;
				a[n].p=p;
				splay(n);
				return;
			}
		}
		else
		{
			now=ls(now);
			if(!now)
			{
				ls(++n)=rs(n)=fa(n)=0;
				fa(n)=ver;
				ls(ver)=n;
				val(n)=val;
				a[n].p=p;
				splay(n);
				return;
			}
		}
	}
	return;
}
inline ll findmax()
{
	re ll now=root;
	while(rs(now))
		now=rs(now);
	re ll tmp=val(now);
	if(ls(now))
	{
		connect(ls(now),fa(now),1);
		splay(ls(now));
	}
	else
		a[fa(now)].son[1]=0;
	destroy(now);
	return tmp;
}
inline ll findmin()
{
	re ll now=root;
	while(ls(now))
		now=ls(now);
	re ll tmp=val(now);
	if(rs(now))
	{
		connect(rs(now),fa(now),0);
		splay(rs(now));
	}
	else
		a[fa(now)].son[0]=0;
	destroy(now);
	return tmp;
}
signed main()
{
	while(true)
	{
		read(op);
		if(!op)
			break;
		if(op==1)
		{
			read(k);
			read(p);
			insert(k,p);
		}
		else if(op==2)
			printf("%lld\n",findmax());
		else
			printf("%lld\n",findmin());
	/*	for(re int i=1;i<=n;i++)
		{
			cout<<val(i)<<" "<<a[i].p<<endl;
			cout<<fa(i)<<" "<<ls(i)<<" "<<rs(i)<<endl; 
		}*/
	}
	exit(0);
}