ext 库在 OI 中的应用

写一个帖子，防止以后忘了。

pb_ds 部分

pb_ds 万能头

#include<bits/extc++.h>

来包含 ext 库中所有的头文件（例如 pb_ds 和 rope）。

但是这句话在非 Ubuntu 环境下可能会显示缺失 iconv.h。 这个在 OI 是可以使用的，因为评测机的 NOI-linux2.0 是 Ubuntu 环境，但如果你考试不开虚拟机是不可以在 Windows 下运行的。

优先队列

由于常数的优劣性，本文只介绍 pairing_heap_tag 配对堆。

然而定义却比较复杂。

示例定义：

#include<bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;

__gnu_pbds::priority_queue<int,greater<int>> a,c;//定义类型
__gnu_pbds::priority_queue<int> d;//默认大根堆

__gnu_pbds::priority_queue<int>::point_iterator it;//定义指针

struct node
{
    int x,y;
    bool friend operator <(const node a,const node b)
    {
        return a.x+a.y<b.x+b.y;
    }
};
__gnu_pbds::priority_queue<node> b;

int main()
{
    a.push(1),a.push(2),a.push(3);
    cout<<a.top()<<"\n";//输出 1

    c.join(a);
    cout<<a.size()<<"\n";//输出 0
    cout<<c.size()<<"\n";//输出 3
    cout<<c.top()<<"\n";//输出 1

    c.pop();
    cout<<c.top()<<"\n";//输出 2

    d.push(1),it=d.push(2),d.push(3);
    cout<<d.top()<<"\n";//输出 3

    d.modify(it,10);
    cout<<d.top()<<"\n";//输出 10

    b.push({1,1}),b.push({2,2}),b.push({3,3});
    cout<<b.top().x<<"\n";//输出 3
}

可以完全替代普通左偏树。

平衡树

失效保证（invalidation_guarantee）

pb_ds 提供了三种失效保证（不是所有的容器的有三种），分别是：

basic_invalidation_guarantee - 基本失效保证，最弱的无效保证。可以保证在容器没有修改时候迭代器，指针等保持有效。

Ps：没有修改的情况下，指针所指的元素还是原来的元素。

point_invalidation_guarantee - 点失效保证，更强的无效保证。可以保证在修改容器但迭代器等所指的东西没有被删除是保持有效。

Ps：修改后，如果修改的不是指针所指的元素，那么指针所指的元素还是原来的元素。

range_invalidation_guarantee - 范围失效保证，最强的无效保证。在 点失效保证 的基础上，保证相对位置不变。

Ps：修改后，如果修改的不是指针所指的元素，那么指针所指的元素还是原来的元素；同时，保证指针的相对位置不变。

pairing_heap_tag 均为点失效保证。

rb_tree_tag 为范围失效保证。

其他

ROPE

参考文献

堆 - OI Wiki

平衡树 - OI Wiki

浅谈 pb_ds 库及其在 OI/其他算竞中的应用

鸽一下……