【ZOJ2334】Monkey King

鲜于阳

2023-12-01

题目大意

有 $n(n≤10^5)$ 只猴子，初始每只猴子为自己猴群的猴王，每只猴子有一个初始的力量值。这些猴子会有 $m$ 次会面。每次两只猴子 $x,y$ 会面，若 $x,y$ 属于同一个猴群输出 $−1$ ，否则将 $x,y$ 所在猴群的猴王的力量值减半，然后合并这两个猴群。新猴群中力量值最高的为猴王。输出新猴王的力量值。

简要分析

我们需要一种数据结构维护元素，支持快速合并，查找最大值。普通的堆并不能快速合并，所以大神们搞出了可并堆这种东西。
左偏树是一种比较好写的可并堆，详细请看BYVOID大神（黑科技：pbds库里有可并堆模板哦！）

AC code :

#include <set>
#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> pii;

inline int read()
{
    int x = 0; int v = 1, c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') v = -1;
    for(;c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
    return x * v;
}

template<typename T>
inline void write(T x, int ch = 10)
{
    int s[20], t = 0;
    if(x < 0) { x = -x; putchar('-'); }
    do s[t++] = x % 10; while(x /= 10);
    while(t--) putchar('0' + s[t]);
    putchar(ch);
}

const int maxn = 100005;

int n, m, v[maxn];
int lc[maxn], rc[maxn], d[maxn], fa[maxn];

void input()
{
    for(int i = 1; i <= n; ++i)
        v[i] = read();
    m = read();
}

inline void clear(const int &x)
{
    d[x] = lc[x] = rc[x] = 0;
}

inline void reset(const int &x)
{
    fa[x] = x;
}

void build()
{
    for(int i = 1; i <= n; ++i)
    {
        reset(i);
        clear(i);
    }
}

int getfa(const int &x)
{
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

int merge(int a, int b)
{
    if(a == 0) return b;
    if(b == 0) return a;
    if(v[a] < v[b]) swap(a, b);
    rc[a] = merge(rc[a], b);
    if(rc[a]) fa[rc[a]] = a;
    if(d[lc[a]] < d[rc[a]]) swap(lc[a], rc[a]);
    d[a] = rc[a] ? d[rc[a]] + 1 : 0;
    return a;
}

int pop(int x)
{
    int l = lc[x], r = rc[x];
    reset(l); reset(r);
    reset(x); clear(x);
    return merge(l, r);
}

int modify(int x)
{
    v[x] >>= 1;
    return merge(x, pop(x));
}

void solve()
{
    register int x, y, z;
    for(int i = 1; i <= m; ++i)
    {
        x = getfa(read()); y = getfa(read());
        if(x == y) puts("-1");
        else
        {
            x = modify(x);
            y = modify(y);
            z = merge(x, y);
            write(v[z]);
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    while(~scanf("%d", &n))
    {
        input();
        build();
        solve();
    }

#ifndef ONLINE_JUDGE
    fprintf(stderr, "Run Time: %dms\n", clock());
    fclose(stdin), fclose(stdout);
#endif
    return 0;
}

题外话(黑科技)

使用pbds中的可并堆

一点介绍

原文在这里
包含：ext/pb_ds/priority_queue.hpp
声明：__gnu_pbds::priority_queue
模板参数：

template < typename Value_Type ,
    typename Cmp_Fn = std :: less < Value_Type >,
    typename Tag = pairing_heap_tag ,
    typename Allocator = std :: allocator <char > >
class priority_queue

Value_Type：类型
Cmp_Fn：自定义比较器
Tag：堆的类型。可以是

binary_heap_tag（二叉堆）
binomial_heap_tag（二项堆）
rc_binomial_heap_tag 
pairing_heap_tag（配对堆）
thin_heap_tag

Allocator：不用管

使用

相比STL中的priority_queue，可以

用begin()和end()获取迭代器从而遍历
删除单个元素

void erase(point_iterator)

增加或减少某一元素的值

void modify(point_iterator, const_reference)

合并，把other合并到*this，并把other清空

void join(priority_queue &other)

性能分析

五种操作：push、pop、modify、erase、join

pairing_heap_tag：push和join $O(1)$ ，其余均摊 $O(logn)$
binary_heap_tag：只支持push和pop，均为均摊 $O(logn)$
binomial_heap_tag：push为均摊 $O(1)$ ，其余为 $O(logn)$
rc_binomial_heap_tag：push为 $O(1)$ ，其余为 $O(logn)$
thin_heap_tag：push为 $O(1)$ ，不支持join，其余为 $O(logn)$ ；但是如果只有increase_key，modify均摊 $O(1)$
不支持不是不能用，而是用起来很慢

黑科技演示

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;

inline int read()
{
    int x = 0; int v = 1, c = getchar();
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') v = -1;
    for(;c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
    return x * v;
}

template<typename T>
inline void write(T x, int ch = 10)
{
    int s[20], t = 0;
    if(x < 0) { x = -x; putchar('-'); }
    do s[t++] = x % 10; while(x /= 10);
    while(t--) putchar('0' + s[t]);
    putchar(ch);
}

const int maxn = 100005;

int n, m, v[maxn];
int fa[maxn];
priority_queue<int> q[maxn];

int getfa(const int &x)
{
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

void input()
{
    for(int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        v[i] = read();
        q[i].clear();
        q[i].push(v[i]);
    }
    m = read();
}

void solve()
{
    register int x, y, z;
    for(int i = 1; i <= m; ++i)
    {
        x = getfa(read()); y = getfa(read());
        if(x == y) puts("-1");
        else
        {
            z = q[x].top();
            q[x].pop();
            q[x].push(z >> 1);
            z = q[y].top();
            q[y].pop();
            q[y].push(z >> 1);
            fa[y] = x;
            q[x].join(q[y]);
            write(q[x].top());
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    while(~scanf("%d", &n))
    {
        input();
        solve();
    }

#ifndef ONLINE_JUDGE
    fclose(stdin), fclose(stdout);
#endif
    return 0;
}