题解：P11266 【模板】完全体·堆

由于发现没人写平衡树，于是就有了这篇题解。

核心思路

不妨用

n

棵平衡树

t_1\dots t_n

维护

n

个集合，使用值作为键、出现次数作为值，那么各操作分别等同于：

0 x y：如果 $t_{x,a_y}=1$ 则删除这一项，否则将其值减一。
1 x：输出 $t_x$ 第一项的键。
2 x y：枚举 $t_y$ 的每一项 $(k,v)$ ，如果存在 $t_{x,k}$ 则令 $t_{x,k}\gets t_{x,k}+v$ ，否则在 $t_x$ 中插入这一项，然后清空 $t_y$ 。
3 x y z：相当于先执行 0 x y，再将 $a_y$ 设为 $z$ ，然后若存在 $t_{x,z}$ 则将其值增加一，否则在 $t_x$ 中插入 $(z,y)$ 。

考虑使用 __gnu_pbds::tree 或 std::map 维护可过。

参考代码

CPP

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

int n, m, a[1000024];

tree<int, int> t[1000024];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        t[i].insert({a[i], 1});
    }
    int tp, x, y, z;
    while (m--) {
        scanf("%d %d", &tp, &x);
        if (tp == 0) {
            scanf("%d", &y);
            if (t[x][a[y]] == 1) t[x].erase(a[y]);
            else t[x][a[y]]--;
        }
        else if (tp == 1) {
            printf("%d\n", t[x].begin()->first);
        }
        else if (tp == 2) {
            scanf("%d", &y);
            for (auto&[k, v] : t[y]) {
                auto it = t[x].find(k);
                if (it != t[x].end()) it->second += v;
                else t[x].insert({k, v});
            }
            t[y].clear();
        }
        else if (tp == 3) {
            scanf("%d %d", &y, &z);
            if (t[x][a[y]] == 1) t[x].erase(a[y]);
            else t[x][a[y]]--;
            a[y] = z;
            auto it = t[x].find(z);
            if (it != t[x].end()) it->second++;
            else t[x].insert({z, 1});
        }
    }
    return 0;
}

题解：P11266 【模板】完全体·堆

文章操作

核心思路

参考代码

相关推荐

评论

题解：P11266 【模板】完全体·堆