hdu5818

题解：

维护两个左偏树

按照左偏树模板来做

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

char s1[],s2[];

int rt[],tot,size[N],cas,dist[N],x,y,c[N][],n,a[N],val[N];

int merge(int x,int y)

{

    if (!x||!y)return x+y;

    if (val[x]<val[y])swap(x,y);

    c[x][]=merge(c[x][],y);

    if (dist[c[x][]]<dist[c[x][]])swap(c[x][],c[x][]);

    dist[x]=dist[c[x][]]+;

    return x;

}

int newnode(int x,int y)

{

    val[++tot]=x;a[tot]=y;

    size[tot]=;

    c[tot][]=c[tot][]=dist[tot]=;

    return tot;

}

int main()

{

    while (~scanf("%d",&n),n)

     {

         printf("Case #%d:\n",++cas);

         rt[]=rt[]=tot=;

         memset(val,,sizeof val);

         memset(size,,sizeof size);

         memset(c,,sizeof c);

         for (int i=;i<=n;i++)

          {

              scanf("%s",&s1);

              if (s1[]=='u')

               {

                   scanf("%s%d",&s2,&y);

                   if (s2[]=='A')x=;

                   else x=;

                   rt[]=newnode(i,y);

                   rt[x]=merge(rt[x],rt[]);

               }

              if (s1[]=='o')

             {

                   scanf("%s",&s2);

                   if (s2[]=='A')x=;

                   else x=;

                   printf("%d\n",a[rt[x]]);

                   rt[x]=merge(c[rt[x]][],c[rt[x]][]);

             }

            if (s1[]=='e')

             {

                 scanf("%s%s",&s2,&s2);

                 if (s2[]=='B')x=;

                 else x=;

                 rt[x]=merge(rt[x],rt[-x]);

                 rt[-x]=c[-x][]=c[-x][]=size[-x]=dist[-x]=;

             }

          }

     }

}