DDOSvoid's Blog

堆

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

简介

世界上并不存在堆，只有左偏树和 $priority\underline{}queue$

实现

小根堆

1
priority_queue<int, vector<int>, greater<int>> Q;

自定义堆

1
2
3
4
5
6
7
struct cmp {
    bool operator () (int x, int y) const {
        return x > y;
    }
} ;

priority_queue<int, vector<int>, cmp> Q;

可删除堆

其实就是写两个 $priority\underline{}queue$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename T>
struct Heap {
    T add, del;

    inline void push(int x) { add.push(x); }

    inline void erase(int x) { del.push(x); }

    inline int top() {
        while (!del.empty() && del.top() == add.top()) del.pop(), add.pop();
        return add.top();
    }

    inline void pop() {
        while (!del.empty() && del.top() == add.top()) del.pop(), add.pop();
        add.pop();
    }

    inline bool empty() { return add.size() - del.size() == 0; }
    
    inline int size() { return add.size() - del.size(); }
};
Heap<priority_queue<int>> Qmax;
Heap<priority_queue<int, vector<int>, greater<int>>> Qmin;

应用

  1. 超级钢琴类

    大概就是题目要求前 $k$ 大的贡献和

    我们将其分成若干不相交的几部分

    每一部分先扔最大值到堆里，每次取出第 $i$ 大值之后扔进去第 $i+1$ 大值，不过一定要保证第 $i$ 大的贡献要大于第 $i+1$ 大

    下面的 CF 1428E Carrots for Rabbits 就先证明了这东西

    Luogu P2048 [NOI2010]超级钢琴

    Luogu P1392 取数 稍微有点不一样

    Luogu P5283 [十二省联考2019]异或粽子

    CF 1428E Carrots for Rabbits

  2. 维护前 $k$ 大

    用两个堆，一个大根堆，一个小根堆

    Luogu P1801 黑匣子