over 4 years ago

左偏树模板题

题意:M x y 合并x与y所在集合
K x 删掉x所在集合中最小的那个点
M操作一看就是一个并查集。但是k操作不能使用并查集。发现左偏树可以维护最值且可以合并。
所以在这里并查集只是用来快速的查找两个的点的所在集合的左偏树顶点
1A果然爽

#include<cstdio>
#include<cstring> 
#include<cstdlib>
#include<algorithm>
#define maxn 1000100
#define l(x) son[x][0]
#define r(x) son[x][1]
using namespace std;
int n,m;
bool can[maxn];
int fa[maxn],son[maxn][2],num[maxn],root[maxn],d[maxn];
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-')c=getchar(),bj=-1;
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
int merge(int x,int y)
{
    if (x==0||y==0) return x+y;
    if (num[x]>num[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)]+1;
    return x;
}
int pop(int now)
{
    now=merge(l(now),r(now));
    return now;
}
int find(int x)
{
    if (fa[x]==x) return x;else return fa[x]=find(fa[x]);
}
int main()
{
    int i,j,x,y;char c;
    n=readln();
    memset(can,true,sizeof(can));
    for (i=1;i<=n;i++) num[i]=readln(),fa[i]=i,root[i]=i;
    m=readln();
    while (m--)
    {
        c=getchar();
        while (c!='M'&&c!='K') c=getchar();
        if (c=='M')
        {
            x=readln();y=readln();
            if (!can[x]||!can[y]) continue;
            x=find(x);y=find(y);
            if (x!=y)
            {
                root[x]=merge(root[x],root[y]);
                fa[y]=x;
            }
        }
        if (c=='K')
        {
            x=readln();
            if (!can[x]){printf("0\n");continue;}
            x=find(x);
            can[root[x]]=false;
            printf("%d\n",num[root[x]]);
            root[x]=pop(root[x]);
        }
    }
}
← zkw费用流 点分治 【poj1741&&bzoj1499】 →
 
comments powered by Disqus