pb_ds

在放代码之前，先介绍一个库—— pbds（Policy-Based Data Structures），这是一个 GNU C++ STL 的扩展库，提供了增强版数据结构，包括优先队列，平衡树。

在 pbds 库中，有一个容器，叫 tree，是一种平衡二叉搜索树，可以支持按排名访问元素。

tree 容器

定义

template<
    typename Key,                           // 元素类型
    typename Mapped,                        // 映射值类型 (相当于 map 的映射值)，模拟 set 时无需该项，设为 null_type即可
    typename Cmp_Fn,                        // 比较函数，例如 less<Key> 等，也可以使用自定义比较函数
    typename Tag,                           // 树类型 rb_tree_tag（红黑树，默认是这个） / splay_tree_tag
    template<typename Const_Node_Iterator,
             typename Node_Iterator,
             typename Cmp_Fn_,
             typename Allocator_>class Node_Update // 节点更新策略，例如 tree_order_statistics_node_update
>class tree;

使用前提

• 需要包含<ext/pb_ds/assoc_container.hpp>，<ext/pb_ds/tree_policy.hpp> 头文件（注意，万能头文件中一般不含这两个头文件）。
• 使用 find_by_order 或 order_of_key 函数时，必须使用 tree_order_statistics_node_update 策略。
• 默认去重，重复元素需用 pair<value,unique number> 处理。

核心功能/函数

功能	函数	说明	返回值/类型	时间复杂度 *
插入元素	insert(x)	插入元素 x（唯一）	void	O(log n)
删除元素	erase(x)	删除值等于 x 的元素	void	O(log n)
查找元素	find(x)	返回迭代器	iterator	O(log n)
查找第 k 小	find_by_order(k)	返回第 k 小元素，0-index	iterator	O(log n)
查询排名	order_of_key(x)	返回严格小于 x 的元素数量	int	O(log n)
大小	size()	当前元素个数	int	O(1)
是否为空	empty()	检查是否为空	bool	O(1)
清空	clear()	删除所有元素	void	O(n)

*：时间复杂度是在 rb_tree_tag 的基础上计算的。

---

『题解』A21561中位数

题目大意

题目等价于：动态维护前i个元素的有序序列，快速取第k小元素。

• 中位数的下标 $\displaystyle k=\frac{i}{2}$ (1-indexed)。
• 输入 $N \le 1 0^{5}$，元素范围 $0 \le A_{i}\le 1 0^{9}$。

代码实现

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;//使用 __gnu_pbds 命名空间
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>s;//定义一棵平衡树
signed main() 
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) 
    {
        int x;
        cin>>x;
        s.insert({x,i});//将每一个值插入树中，i 避免重复
        if(i%2==1) //如果是奇数项
        {
            cout<<s.find_by_order(i/2)->first<<"\n";//输出排名为 i/2 的项的值，即前 1~i 位的中位数
        }
    }
    return 0;
}

时间复杂度

$\mathcal{O}(n \log n)$。