題目大意:給定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); } } }