BZOJ 1455: 罗马游戏 – [可并堆/左偏树] [模版]

题目传送门(BZOJ)
>原文链接<

题解 :

​ 唔,看上去我们需要维护一个资瓷合并、实时查询更新最小值的数据结构。

—— 可并堆可以胜任这项任务。

​ 可并堆是一个堆式结构的二叉树,由于其左偏的性质,有类似启发式合并的复杂度 —— 单次操作 \Theta(\log n)

我们只要维护如下几个性质就好 :

  • $val[p] \le val[ls[p]] \& val[p] \le val[rs[p]]$
  • $dis[ls] \ge dis[rs]$
  • $dis[p] = dis[rs]+1$

满足后两个性质,意味着 dis[p] \le \log n 满足第一个性质,意味着它是一个堆。

现在我们考虑如何合并、合并的复杂度是什么

合并的复杂度是 \log siz[x] + \log siz[y]

合并两个堆,只要比较当前节点权值,而后将权值较大的与另一个点的右子树递归合并即可, 当合并的两个点有一个点不存在。即上一层没有右儿子,直接把这个点接到上一层点上,做其右儿子就好。

代码 :

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1100000;
int ls[N], rs[N], dis[N], val[N], fa[N], Kill[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int merge(int x, int y) {
    if((!x)|(!y)) return x+y;
    if(val[x] > val[y]) swap(x, y);
    rs[x] = merge(rs[x], y);
    if(dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1;
    return x; 
}
int main() {
    int n, m;
    scanf("%d", &n); for(int i = 1; i <= n; i ++ ) scanf("%d", &val[i]), fa[i] = i;
    scanf("%d", &m);
    while(m -- ) {
        char opt[3];
        scanf("%s", opt);
        if(opt[0] == 'M') {
            int x, y;
            scanf("%d%d", &x, &y);
            if(Kill[x] | Kill[y]) continue;
            int dx = find(x), dy = find(y);
            if(dx != dy) fa[dx] = fa[dy] = merge(dx, dy);
        }
        else {
            int x;
            scanf("%d", &x);
            if(Kill[x]) {
                puts("0");
                continue;
            }
            int dx = find(x);
            printf("%d\n", val[dx]);
            fa[dx] = fa[ls[dx]] = fa[rs[dx]] = merge(ls[dx], rs[dx]);
            Kill[dx] = 1;
        }
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注