[总结][左偏树]BZOJ2809,1455

左偏树又叫做可合并堆,比较容易理解,也比较好写。。

它并不是真正的堆,虽然是二叉树,但并不是完全二叉树,也并不平衡。

核心操作在于将两颗左偏树合并为一颗左偏树。

首先确定维护的是集合的最大值还是最小值。

然后就是随便搞搞。。。

推荐05年集训队论文,很简单易懂。

目前还没有掌握删除左偏树中任意指定节点的方法。。。
【BZOJ2809】

就是求出一个节点,选出以其为根的子树中自己之外的一些点,使他们的花费和不超过给定值,定义这个节点的贡献值为他的领导力与选出的点的最大个数,求出所有节点贡献值的最大值。

由底至上进行统计,维护大根可合并堆,并记录当前左偏树的花费和以及点的总数,对于当前节点,首先贪心地把全部子节点加入左偏树中,再不断删除根,直到花费和不超过给定值。此时更新答案。

【代码】

#include<cstdio>
#include<cstring>
#include<cctype>
#define N (100010)
typedef long long LL;
inline LL max(LL a , LL b)
{
    return a > b ? a : b;
}
inline char getc()
{
    static const int L = 1 << 15;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint()
{
    static char c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
int weigh[N] , root[N] , cost[N] , size[N] , d[N] , l[N] , r[N];
LL addcost[N];
inline void swap(int &x , int &y)
{
    int tmp = x;
    x = y;
    y = tmp;
}
inline int merge(int x , int y)
{
    if (!x || !y)
        return x + y;
    if (cost[x] < cost[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 head[N] , next[N];
int main()
{
    int n , M;
    n = getint();
    M = getint();
    register int i , j , k;
    int pa;
    for(i = 1 ; i <= n ; ++i)
    {
        size[i] = 1;
        pa = getint();
        root[i] = i;
        next[i] = head[pa];
        head[pa] = i;
        cost[i] = getint();
        addcost[i] = cost[i];
        weigh[i] = getint(); 
    }
    LL ans = 0;
    for(i = n ; i ; --i)
    {
        for(j = head[i] ; j ; j = next[j])
        {
            addcost[i] += addcost[j];
            size[i] += size[j];
            root[i] = merge(root[i] , root[j]);
        }
        while(addcost[i] > M)
        {
            addcost[i] -= cost[root[i]];
            --size[i];
            root[i] = merge(l[root[i]] , r[root[i]]);
        }
        ans = max(ans , (LL)size[i] * weigh[i]);
    }
    printf("%lld" , ans);
    return 0;
}

【BZOJ1455】

利用并查集维护当前节点所在左偏树的根。

此外,删除最小根时,只需进行将根的root指向根的左右子树合并后的根,再令根的root的root指向根的root。

【代码】

#include<cstdio>
#include<cstring>
#include<cctype>
inline char getc()
{
    static const int L = 1 << 15;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint()
{
    static char c;
    while(!isdigit(c = getc()));
    int tmp = c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
inline char getch()
{
    static char c;
    while((c = getc()) != 'K' && c != 'M');
    return c;
}
#define N (1000010)
inline void swap(int &x , int &y)
{
    int tmp = x;
    x = y;
    y = tmp;
}
int weigh[N] , root[N] , l[N] , r[N] , d[N];
int find(int x)
{
    if (x == root[x])
        return x;
    root[x] = find(root[x]);
    return root[x];
}
int merge(int x , int y)
{
    if (!x || !y)
        return x + y;
    if (weigh[x] > weigh[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;
}
bool exist[N];
int main()
{
    int n = getint();
    register int i , j , k;
    for(i = 1 ; i <= n ; ++i)
    {
        weigh[i] = getint();
        root[i] = i;
        exist[i] = 1;
    }
    int ask = getint();
    while(ask--)
    {
        char sign = getch();
        if (sign == 'K')
        {
            int a = getint();
            if (!exist[a])
            {
                puts("0");
                continue;
            }
            else
            {
                int tmproot = find(a);
                printf("%d\n" , weigh[tmproot]);
                exist[tmproot] = 0;
                root[tmproot] = merge(l[tmproot] , r[tmproot]);
                root[root[tmproot]] = root[tmproot];
            }
        }
        else
        {
            int a = getint();
            int b = getint();
            if (!exist[a] || !exist[b])
                continue;
            int tmpa = find(a);
            int tmpb = find(b);
            if (tmpa == tmpb)
                continue;
            root[tmpa] = root[tmpb] = merge(tmpa , tmpb);
        }
    }
    return 0;
}
comments powered by Disqus