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

Mrkn_chenyx12 · 2024-11-18 20:05:34 · 题解

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

核心思路

不妨用 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 维护可过。

参考代码

#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;
}