ZOJ2334-Monkey King【二项堆】

这道题网上一搜全是左偏树。囧。因为某天我nc的打开算导看起了二项堆，然后隐隐约约看会了。然后就发现不用二项堆写这道题就不舒服了。囧。
搜到一个用二项堆写的。结果是p党。代码冗长。不忍直视。果断ctrl+w放弃。最后无奈只能在算导的熏陶下自己写了。

言归正传。

题意：一开始n个集合。每个集合里一个数。每次选中两个集合，把这两个个集合的最大值都除以2。然后把这两个集合合并。输出这个集合的最大值。
分析：那么这就是一个最裸的可合并堆的题。

二项堆是一个神奇的东西。所有可并堆的操作都可以O(logn)。打算之后有空学fib堆。那种除了删元素logn其他都O(1)的神器。。
二项堆如果不会请移步算导。
首先要了解二项树。一个包含n个元素的二项堆是由k个二项树组成的。（k=n转化为2进制后数位上1的个数）那么k是logn级别的。
其中每颗二项树都满足堆的性质。比如这道题，每颗二项树的根是整棵二项树中的最大值。那么查询的时候只要遍历一遍二项堆的所有根节点就可以确定最大值。因此查询是O(logn)。
修改的时候。先通过并查集找到两个点对应的二项堆。对这两个堆分别操作：找到最大值的根节点。把这个根对应的值除以2。然后把这整棵二项树提出来。把根节点和子孙全断掉，然后子孙之间反过来拼接到根节点的后面。（具体可以详见算导，这太意识流了）然后再和原来的二项堆合并。合并的时候先归并排序合并O(logn)，再进行调整O(logn)，因此合并的复杂度是O(logn)。所以整个修改过程都是O(logn)。
那么整道题就是O(nlogn)了。

写了两天才A掉。（一定是我太没效率了。。T.T囧

最后结果出人意料的rank9。尽然把左偏树艹掉了？二项堆神奇啊。或许这是快速读入的胜利？

 

?
ZOJ2334
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int Fa[maxn],F[maxn],ch[maxn],key[maxn],deg[maxn],n1[maxn],tmp[25],n;
inline int GF(int x){  return x==Fa[x]?x:Fa[x]=GF(Fa[x]);}
inline int UN(int u,int v){
    int uu=GF(u),vv=GF(v);
    if(uu<vv)   Fa[uu]=vv;  else    Fa[vv]=uu;
}inline void link(int x,int y){
    n1[x]=ch[y];    ch[y]=x;    deg[y]++;
}int merge(int x,int y){
    int ret=deg[x]<=deg[y]?x:y,p=ret;
    if(p==x)    x=n1[x];    else    y=n1[y];
    while(x!=-1 || y!=-1){
        if(x==-1)       p=(n1[p]=y),  y=n1[y];
        else if(y==-1)  p=(n1[p]=x),  x=n1[x];
        else{
            if(deg[x]<=deg[y])  p=(n1[p]=x),  x=n1[x];
            else                p=(n1[p]=y),  y=n1[y];
        }
    }n1[p]=-1;  return ret;
}int un(int u,int v){
    if(u==-1)   return v;   if(v==-1)   return u;
    int ret=merge(u,v),p=-1,x=ret,s=n1[x];
    while(s!=-1){
        if(deg[x]!=deg[s] || (n1[s]!=-1 && deg[n1[s]]==deg[x])) p=x,x=s;
        else if(key[x]>=key[s]) n1[x]=n1[s],link(s,x);
        else{
            if(p==-1)  ret=s;   else    n1[p]=s;
            link(x,s);  x=s;
        }s=n1[x];
    }return ret;
}inline int getmax(int head){
    int ret=-1;
    for(int x=head;x!=-1;x=n1[x])   if(key[x]>ret)  ret=key[x];
    return ret;
}void update(int &head){
    int ret=-1,pre=-1,pos,p;
    for(int x=head;x!=-1;pre=x,x=n1[x])   if(key[x]>ret)  ret=key[x],pos=x,p=pre;
    key[pos]>>=1;
    if(deg[pos]){
        if(p==-1){
            head=n1[head];  int tct=0;
            for(int i=ch[pos];i!=-1;i=n1[i])tmp[++tct]=i;
            ch[pos]=-1; n1[pos]=tmp[tct];   int j=tmp[tct];
            for(int i=tct-1;i>=1;i--)n1[j]=tmp[i],j=tmp[i]; n1[j]=-1;
            deg[pos]=0;
            head=un(pos,head);
        }else{
            n1[p]=n1[pos]; int tct=0;
            for(int i=ch[pos];i!=-1;i=n1[i])tmp[++tct]=i;
            ch[pos]=-1; n1[pos]=tmp[tct];   int j=tmp[tct];
            for(int i=tct-1;i>=1;i--)n1[j]=tmp[i],j=tmp[i]; n1[j]=-1;
            deg[pos]=0;
            head=un(pos,head);
        }
    }
}inline void read(int &x){
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch-'0';
    for(ch=getchar();ch>='0' && ch<='9';ch=getchar())x=x*10+ch-'0';
}int main(){
    int m,u,v;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)read(key[i]),deg[i]=0,ch[i]=n1[i]=-1,F[i]=Fa[i]=i;
        read(m);   
        while(m--){
            read(u);    read(v);
            if(GF(u)==GF(v))  printf("-1\n");
            else{
                update(F[Fa[u]]);   update(F[Fa[v]]);
                int k=un(F[Fa[u]],F[Fa[v]]);    UN(u,v);
                F[Fa[u]]=F[Fa[v]]=k;
                printf("%d\n",getmax(k));
            }
        }
    }return 0;
}

 

ZOJ ZOJ 二项堆 Comments(1) 2013年6月03日 14:38