hdu3031

题解：

左偏树模板题目

每一次合并，删除最大，修改最大

都是基本操作

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int M=,N=;

int T,n,m,p[M],root[M],v1=,v0=,c[N][],dist[N],val[N],cnt;

void makeheap(int x,int v)

{

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

    val[x]=v;

}

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;

}

void ps(int &x){x=merge(c[x][],c[x][]);}

void change(int &x,int v)

{

    int k=merge(c[x][],c[x][]);

    makeheap(x,v);

    x=merge(x,k);

}

int main()

{

    scanf("%d",&T);

    while (T--)

     {

        cnt=;

        scanf("%d%d",&n,&m);

        for (int i=;i<=m;i++)scanf("%d",&p[i]);

        memset(root,,sizeof root);

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

         for (int j=,x;j<=p[i];j++)

          {

            scanf("%d",&x);

            makeheap(++cnt,x);

            root[i]=merge(root[i],cnt);

          }

        int x[],rt[];

        memset(rt,,sizeof rt);

        memset(x,,sizeof x);

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

         {

            char s[];

            int a;

            scanf("%s",&s);

            if (s[]=='T')

             {

                scanf("%d",&a);

                rt[i&]=merge(rt[i&],root[a]);

                x[i&]+=p[a];

             }

            if (s[]=='C')

             {

                if (val[rt[]]==val[rt[]])continue;

                if (val[rt[]]>val[rt[]])

                 {

                    x[]+=x[];

                    x[]=;

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

                    rt[]=;

                 }

                else

                 {

                    x[]+=x[];

                    x[]=;

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

                    rt[]=;

                 }

             }

            if (s[]=='L')

             {

                ps(rt[i&]);

                x[i&]--;

             }

            if (s[]=='A')

             {

                scanf("%d",&a);

                change(rt[i&],val[rt[i&]]+a);

             }

            if (s[]=='E')

             {

                scanf("%d",&a);

                change(rt[i&],a);

             }

         }

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

        if (x[]>=x[])v1++;

        else v0++;

     }

    if (v1<v0)puts("I will be back!!");

    else puts("Hahaha...I win!!");

    return ;

}