[BZOJ1455]罗马游戏（左偏树）

用并查集和左偏树维护士兵的关系

Code

#include <cstdio>
#include <algorithm>
#define N 1000010
using namespace std;

int n,m,fa[N];
bool gg[N];

int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
namespace Lt{
 int l[N],r[N],v[N],d[N];
 int merge(int x,int y){
  if(!x||!y) return x+y;
  if(v[x]>v[y]) swap(x,y);
  r[x]=merge(r[x],y);
  if(d[r[x]]>d[l[x]]) swap(l[x],r[x]);
  d[x]=d[r[x]]+1;
  return x;
 }
 inline int tp(int x){return v[x];}
 inline void pop(int x){
  fa[x]=merge(l[x],r[x]);
  fa[fa[x]]=fa[x];
 }
}

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main(){
 n=read();
 for(int i=1;i<=n;++i) Lt::v[i]=read(),fa[i]=i;
 m=read();
 while(m--){
  char ch;for(ch=getchar();ch!='M'&&ch!='K';ch=getchar());
  if(ch=='K'){
   int x=read(),p;
   if(gg[x]) puts("0");
   else{
    gg[p=Find(x)]=1;
    printf("%d\n",Lt::v[p]);
    Lt::pop(p);
   }
  }else{
   int x=read(),y=read();
   if(gg[x]||gg[y]) continue;
   int px=Find(x),py=Find(y);
   if(px!=py) fa[px]=fa[py]=Lt::merge(px,py);
  }
 }
 return 0;
}

转载于:https://www.cnblogs.com/void-f/p/9168960.html