题解 P3377 【【模板】左偏树（可并堆）】

· · 题解

这题其实就是个可并堆，当然不一定要用左偏树，所以我选择了配对堆（感谢HOOCCOOHdalao的教导）

事实证明配对堆跑的飞快，我没有刻意去卡常（事实上代码写的相当丑），只加了读入优化，但还是跑的比kcz大爷的左偏树还快（嘿嘿嘿成功挤掉kcz大爷的rank1）。

由于这题是一些不相交集合（堆）的合并，所以显然需要用到并查集，具体就是合并两个堆的时候顺便在并查集里也合并了，然后以后通过元素编号访问堆时就去查询并查集里的根节点就是实际的堆的根节点编号（写代码的时候脑子有点糊，并查集写的相当烂）。

配对堆的主要代码HOOCCOOHdalao的题解里都写了，我也是基本参考他的写法。就是要注意的是他提到了维护堆时要比较节点编号，但是没有在他贴的代码里体现出来，一开始我被小小的坑了一下（滑稽）。

然后下面是代码

#include <bits/stdc++.h>
using namespace std;
const int BUF=40000000;
char Buf[BUF],*buf=Buf;
const int OUT=20000000;
char Out[OUT],*ou=Out;int Outn[30],Outcnt;
inline void write(int x){
  if(!x)*ou++=48;
  else{
    for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;
    while(Outcnt)*ou++=Outn[Outcnt--];
  }
}
inline void writechar(char x){*ou++=x;}
inline void writeln(){*ou++='\n';}
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
struct Node
{
    int v,id;
    Node *ch,*xd;
}node[100001];
Node* merge(Node* a,Node* b)
{
    if (a->v==0) return b; if (b->v==0) return a;
    if (a->v>b->v || (a->v==b->v && a>b)) swap(a,b);  //注意在元素值相同时比编号，即把编号当第二关键字
    b->xd=a->ch; a->ch=b;
    return a;
}
Node* merges(Node* c)
{
    if (c->v==0 || c->xd->v==0) return c;
    Node *a=c->xd,*b=a->xd; c->xd=a->xd=node;
    return merge(merge(c,a),merges(b));
}
Node* delMin(Node* x)
{ 
    //printf("%d\n",x->v);
    write(x->v); writeln();
    x->v=-1;
    return merges(x->ch);
}
int fa[100001];
int find(int x)
{
    if (fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool Union(int fx,int fy)
{
    if (fx==fy) return false;
    fa[fy]=fx;
    return true;
}
Node* heap[100001];
bool b[100001];
int main()
{
    fread(Buf,1,BUF,stdin);
    memset(b,true,sizeof(b));
    int n,m;
    //scanf("%d%d",&n,&m);
    read(n); read(m);
    node[0].v=0;
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=n; i++)
    {
    //scanf("%d",&node[i].v);
    read(node[i].v);
    node[i].id=i;
    node[i].ch=node[i].xd=node;
    heap[i]=&node[i];
    }
    for(int i=1; i<=m; i++)
    {
    int op,x;
    //scanf("%d%d",&op,&x);
    read(op); read(x);
    if (op==1)
    {
        int y;
        //scanf("%d",&y);
        read(y);
        int fx=find(x),fy=find(y);
        if (!b[x] || !b[y] || !Union(fx,fy)) continue;
        heap[fx]=merge(heap[fx],heap[fy]);
    }
    else
    {
        int fx=find(x);
        if (!b[x])
        {
        *ou++='-'; *ou++='1'; writeln();
        //printf("-1\n");
        continue;
        }
        b[heap[fx]->id]=false;
        heap[fx]=delMin(heap[fx]);
        //b[x]=false;
    }
    }
    fwrite(Out,1,ou-Out,stdout);
}