题目大意：给定n个点，每个点有一个权值，提供两种操作：

1.将两个点所在集合合并

2.将一个点所在集合的最小的点删除并输出权值

很裸的可并堆 n<=100W 启发式合并不用想了

左偏树就是快啊~

#include
  
   
#include
   
     #include
    
      #include
     
       #define M 1001001 using namespace std; struct abcd{ abcd *ls,*rs; int h,pos,score; abcd(int x,int y); }*null=new abcd(0,0x3f3f3f3f),*tree[M]; abcd :: abcd(int x,int y) { ls=rs=null; if(!null) h=-1; else h=0; pos=x;score=y; } abcd* Merge(abcd *x,abcd *y) { if(x==null) return y; if(y==null) return x; if(x->score>y->score) swap(x,y); x->rs=Merge(x->rs,y); if(x->ls->h
      
       rs->h) swap(x->ls,x->rs); x->h=x->rs->h+1; return x; } int n,m; int fa[M]; bool dead[M]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } void Unite(int x,int y) { x=Find(x);y=Find(y); if(x==y) return ; fa[x]=y; tree[y]=Merge(tree[x],tree[y]); } int main() { //freopen("1455.in","r",stdin); //freopen("1455.out","w",stdout); int i,x,y; char p[10]; cin>>n; for(i=1;i<=n;i++) scanf("%d",&x),tree[i]=new abcd(i,x); cin>>m; for(i=1;i<=m;i++) { scanf("%s",p); if(p[0]=='M') { scanf("%d%d",&x,&y); if(dead[x]||dead[y]) continue; Unite(x,y); } else { scanf("%d",&x); if(dead[x]) { puts("0"); continue; } x=Find(x); printf("%d\n",tree[x]->score); dead[tree[x]->pos]=1; tree[x]=Merge(tree[x]->ls,tree[x]->rs); } } }