题解：
splay操作
读入速度太慢，导致超时。。。
用字符串gets操作
代码：
#pragma GCC optimize(2) #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int N=1100005; char s[100]; int pre[N],tot,q[10],y,data[N],z,size[N]; int aans[N],p,c[N][2],root,n,m,x; void rot(int x) { int y=pre[x],k=(c[y][0]==x); size[y]=size[c[y][k]]+size[c[x][k]]+1; size[x]=size[c[x][!k]]+size[y]+1; c[y][!k]=c[x][k]; pre[c[y][!k]]=y; pre[x]=pre[y]; if(pre[y])c[pre[y]][c[pre[y]][1]==y]=x; c[x][k]=y;pre[y]=x; } void splay(int x,int g) { for(int y=pre[x];y!=g;rot(x),y=pre[x]) if(pre[y]!=g)rot((x==c[y][0])==(y==c[pre[y]][0])?y:x); if(g==0)root=x; } void insert(int x,int q) { int y=root; while(c[y][x>data[y]]) y=c[y][x>data[y]]; data[++tot]=x;aans[tot]=q; c[tot][0]=c[tot][1]=0; pre[tot]=y; if(y)c[y][x>data[y]]=tot; splay(tot,0); } int findmin() { int y=root; while (c[y][0])y=c[y][0]; if (y==root)root=c[y][1],pre[c[y][1]]=0; else c[pre[y]][0]=c[y][1],pre[c[y][1]]=pre[y]; return aans[y]; } int findmax() { int y=root; while (c[y][1])y=c[y][1]; if (y==root)root=c[y][0],pre[c[y][0]]=0; else c[pre[y]][1]=c[y][0],pre[c[y][0]]=pre[y]; return aans[y]; } int main() { while (1) { gets(s); if (s[0]=='0')return 0; if (s[0]=='1') { int z=0,y=0; int i; for (i=2;s[i]>='0'&&s[i]<='9';i++)z=z*10+s[i]-48; i++; for (;s[i]>='0'&&s[i]<='9';i++)y=y*10+s[i]-48; insert(y,z); } if (s[0]=='3')printf("%d ",findmin()); if (s[0]=='2')printf("%d ",findmax()); } }