【BZOJ】1455 罗马游戏

【算法】可并堆(左偏树)

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int l[maxn],r[maxn],fa[maxn],d[maxn],a[maxn],n,m;

bool die[maxn];//0生1死

int find(int x)

{return fa[x]==x?x:fa[x]=find(fa[x]);}

int merge(int x,int y)//返回x和y合并后子树的根

{

    if(!x)return y;

    if(!y)return x;//遇到一边为空节点则把另一边剩余的子树整颗接上去(返回)

    if(a[x]>a[y])swap(x,y);//将根节点更小的树放在左边

    r[x]=merge(r[x],y);//递归合并左树右孩子和右树

    if(d[l[x]]<d[r[x]])swap(l[x],r[x]);//维护左偏性质

    d[x]=d[r[x]]+;//更新节点距离

    return x;//返回新树根

}

int main()

{

    scanf("%d",&n);

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

    for(int i=;i<=n;i++)fa[i]=i;

    d[]=-;//因为后面的空节点都表示为0，因此会多次调用0。

    scanf("%d",&m);

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

     {

         char c=getchar();

         while(c!='M'&&c!='K')c=getchar();

         if(c=='M')

          {

              int x,y;

              scanf("%d%d",&x,&y);

              if(die[x]||die[y])continue;

              int p=find(x),q=find(y);

              if(p!=q)

               {

                   int t=merge(p,q);//t是新根，可能是fa[x]或fa[y]

                   fa[p]=fa[q]=t;//p,q的父亲变为新根，其他点父亲均不变

               }

          }

         else

          {

              int x;

              scanf("%d",&x);

              if(die[x]){printf("0\n");continue;}

              int p=find(x);die[p]=;

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

              fa[p]=merge(l[p],r[p]);//返回新根(l[p]或r[p])，令原根的父亲为新根，由于并查集，不需要再修改

              fa[fa[p]]=fa[p];//注意改变新根的父亲

             //为什么不能直接加个if判断新根左右然后修改左右父亲啊？改完交了RE，存疑……

          }

     }

    return ;

}

另有蒟蒻WA的代码，错误已标注。

WA Code >_<