hdu5818

题解：

维护两个左偏树

按照左偏树模板来做

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200005;
char s1[10],s2[10];
int rt[4],tot,size[N],cas,dist[N],x,y,c[N][2],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][1]=merge(c[x][1],y);
    if (dist[c[x][0]]<dist[c[x][1]])swap(c[x][0],c[x][1]);
    dist[x]=dist[c[x][1]]+1;
    return x;
}
int newnode(int x,int y)
{
    val[++tot]=x;a[tot]=y;
    size[tot]=1;
    c[tot][0]=c[tot][1]=dist[tot]=0;
    return tot;
}
int main()
{
    while (~scanf("%d",&n),n)
     {
         printf("Case #%d:
",++cas);
         rt[1]=rt[2]=tot=0;
         memset(val,0,sizeof val);
         memset(size,0,sizeof size);
         memset(c,0,sizeof c);
         for (int i=1;i<=n;i++)
          {
              scanf("%s",&s1);
              if (s1[1]=='u')
               {
                   scanf("%s%d",&s2,&y);
                   if (s2[0]=='A')x=1;
                   else x=2;
                   rt[3]=newnode(i,y);
                   rt[x]=merge(rt[x],rt[3]);
               }
              if (s1[1]=='o')
             {
                   scanf("%s",&s2);
                   if (s2[0]=='A')x=1;
                   else x=2;
                   printf("%d
",a[rt[x]]);
                   rt[x]=merge(c[rt[x]][0],c[rt[x]][1]);
             } 
            if (s1[1]=='e')
             {
                 scanf("%s%s",&s2,&s2);
                 if (s2[0]=='B')x=1;
                 else x=2;
                 rt[x]=merge(rt[x],rt[3-x]);
                 rt[3-x]=c[3-x][0]=c[3-x][1]=size[3-x]=dist[3-x]=0;
             } 
          } 
     }
}