poj3481

题解：

splay操作

读入速度太慢，导致超时。。。

用字符串gets操作

代码：

#pragma GCC optimize(2)

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

char s[];

int pre[N],tot,q[],y,data[N],z,size[N];

int aans[N],p,c[N][],root,n,m,x;

void rot(int x)

{

    int y=pre[x],k=(c[y][]==x);

    size[y]=size[c[y][k]]+size[c[x][k]]+;

    size[x]=size[c[x][!k]]+size[y]+;

    c[y][!k]=c[x][k];

    pre[c[y][!k]]=y;

    pre[x]=pre[y];

    if(pre[y])c[pre[y]][c[pre[y]][]==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][])==(y==c[pre[y]][])?y:x);

    if(g==)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][]=c[tot][]=;

    pre[tot]=y;

    if(y)c[y][x>data[y]]=tot;

    splay(tot,);

}

int findmin()

{

    int y=root;

    while (c[y][])y=c[y][];

    if (y==root)root=c[y][],pre[c[y][]]=;

    else c[pre[y]][]=c[y][],pre[c[y][]]=pre[y];

    return aans[y];

}

int findmax()

{

    int y=root;

    while (c[y][])y=c[y][];

    if (y==root)root=c[y][],pre[c[y][]]=;

    else c[pre[y]][]=c[y][],pre[c[y][]]=pre[y];

    return aans[y];

}

int main()

{

    while ()

     {

         gets(s);

         if (s[]=='')return ;

         if (s[]=='')

         {

             int z=,y=;

             int i;

             for (i=;s[i]>=''&&s[i]<='';i++)z=z*+s[i]-;

             i++;

             for (;s[i]>=''&&s[i]<='';i++)y=y*+s[i]-;

            insert(y,z);

         }

         if (s[]=='')printf("%d\n",findmin());

         if (s[]=='')printf("%d\n",findmax());

     }

}