洛谷 P1801 黑匣子（对顶堆 or Treap 动态求解第 k 大值）

Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 i i i。最开始的时候 Black Box 是空的．而 i = 0 i=0 i=0。这个 Black Box 要处理一串命令。

命令只有两种：

• ADD(x)：把 x x x 元素放进 Black Box;

• GET： i i i 加 1 1 1，然后输出 Black Box 中第 i i i 小的数。

记住：第 i i i 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 i i i 个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 m m m 个，GET 命令共有 n n n 个。现在用两个整数数组来表示命令串：

1. a 1 , a 2 , ⋯   , a m a_1,a_2,cdots,a_m a1​,a2​,⋯,am​：一串将要被放进 Black Box 的元素。例如上面的例子中 a = [ 3 , 1 , − 4 , 2 , 8 , − 1000 , 2 ] a=[3,1,-4,2,8,-1000,2] a=[3,1,−4,2,8,−1000,2]。

2. u 1 , u 2 , ⋯   , u n u_1,u_2,cdots,u_n u1​,u2​,⋯,un​：表示第 u i u_i ui​ 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 u = [ 1 , 2 , 6 , 6 ] u=[1,2,6,6] u=[1,2,6,6] 。输入数据不用判错。

第一行两个整数 m m m 和 n n n，表示元素的个数和 GET 命令的个数。

第二行共 m m m 个整数，从左至右第 i i i 个整数为 a i a_i ai​，用空格隔开。

第三行共 n n n 个整数，从左至右第 i i i 个整数为 u i u_i ui​，用空格隔开。

输出 Black Box 根据命令串所得出的输出串，一个数字一行。

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

3
3
1
2

• 对于 30 % 30% 30% 的数据， 1 ≤ n , m ≤ 1 0 4 1 leq n,m leq 10^{4} 1≤n,m≤104。
• 对于 50 % 50% 50% 的数据， 1 ≤ n , m ≤ 1 0 5 1 leq n,m leq 10^{5} 1≤n,m≤105。
• 对于 100 % 100% 100% 的数据， 1 ≤ n , m ≤ 2 × 1 0 5 , ∣ a i ∣ ≤ 2 × 1 0 9 1 leq n,m leq 2 times 10^{5},|a_i| leq 2 times 10^{9} 1≤n,m≤2×105,∣ai​∣≤2×109，保证 u u u 序列单调不降。

• 题意：

实现 动态求解序列的第 k 大数。（注意 k 值是动态变化的）

• 思路：

首先看到这题，应该要立马反应过来这是一道 平衡树Treap 的模板题

（虽然题目的标签是 优先队列，好像还可以用 主席树，不过主席树是动态求 区间第 k 大数，用在本题还是有些大材小用了。主席树还没学，以后再说）

因此一开始就可以用 Treap的模板 a 掉它。

没有学过 Treap 的，可以看看 我之前写过的博客，这里就不再细讲。

对于本题，我们来引入一种新的做法：对顶堆。

我们完全可以类比一下之前在做 AcWing 128. 编辑器 时的 “对顶栈” 做法，对着题目中给出的样例进行模拟，猜测对顶堆具体的模拟过程是怎样的，即：如何实现 动态求解序列的第 k 大值。

对顶堆具体做法：（核心！）

仔细回想一下优先队列的相关知识，我们可以知道，优先队列虽然不支持任意点访问，但我们可以仅花 O(1) 的时间 查询出堆顶的元素，所以我们可以通过维护 对顶堆的两个堆 来进行整个当前维护序列单调性的维护。

众所周知，如果有 两个集合 A 和 B，如果 集合 A 中的最大值 比 集合 B 中的最小值还小，那么我们就能知道：集合 A 中的所有元素都比集合 B 中的元素小。根据这一方法，我们就可以想到：

我们可以设置两个堆，一个大根堆 max_heap（对应集合 A），一个小根堆 min_heap（对应集合 B）。 我们再将假设 已经排好序的集合 A 从 第 k 大的元素 和 第 k + 1 大的元素 之间 “切成两份”，分别存在 大小根堆 中，再根据优先队列的特点可以得知：前 k 大的元素存在大根堆 max_heap中，后面的元素存在小根堆 min_heap中便可解决这个问题。

既然已经知道原理了，那我们就可以想出方案了：

取最简洁的写法，我们在读入每一个元素的时候，直接将元素压入 大根堆 max_heap 。

再维护一下，保证 大根堆 max_heap里的元素个数为 k，

• 如果 当前元素个数大于 k，就把 大根堆 max_heap的队首元素 压入 小根堆 min_heap；
• 如果 当前元素个数小于 k，就把 小根堆 min_heap的队首元素 压入 大根堆 max_heap；

最后 大根堆 max_heap的队首元素就是我们要求的答案。（序列第 k 大值）

当然，方案不止上面这个，下面两种也是可以的，只不过比赛的时候最好写最为简洁的（上面这种，判断条件更少，更加简洁）。注意，这些方案都是等效的：

• 可以先把 前 k 个数据丢进小根堆 min_heap里，再进行比较，最后维护。

• 还可以先把 第一个数据压入大根堆max_heap里（避免后面出问题），之后，每读入一个数据就 将它与大根堆 max_heap的堆顶元素 进行 比较，如果 小于等于堆顶元素 就把它 压入大根堆 max_heap，否则把它 压入小根堆 min_heap。（不过这个方法显得有些多余了）

当然，题目问的还与上面的经典情况略有不同，依照题意，相当于在上面的基础上改成了 动态变化的 k 值，根据情况做出调整即可。

• 时间复杂度：

O ( n l o g n ) O(nlogn) O(nlogn)

• 代码 I：（对顶堆）

#define _CRT_SECURE_NO_WARNINGS 1
#include 

using namespace std;

#define int long long
int m, n;
const int N = 2e5 + 10;
int a[N];
int op[N];
int st[N];

signed main()
{
	int T = 1; //cin >> T;

	while (T--)
	{
		cin >> m >> n;
		for (int i = 1; i <= m; ++i) scanf("%lld", &a[i]);

		for (int i = 1; i <= n; ++i)
		{
			scanf("%lld", &op[i]), st[op[i]] ++;
		}

		int idx = 0;
		priority_queue max_heap;
		priority_queue, greater> min_heap;

		for (int i = 1; i <= m; ++i)
		{
			max_heap.push(a[i]);

			if (max_heap.size() > (idx + 1) && max_heap.size())
			{
				min_heap.push(max_heap.top());
				max_heap.pop();
			}

			while (st[i])
			{
				++idx;
				printf("%dn", max_heap.top());
				st[i]--;
				if (st[i] && min_heap.size()) {
					max_heap.push(min_heap.top());
					min_heap.pop();
				}
			}

			if (max_heap.size() < (idx + 1) && min_heap.size())
			{
				max_heap.push(min_heap.top());
				min_heap.pop();
			}
		}
	}

	return 0;
}

• 代码 II：（Treap 不做解释，自己看我上方提到的博客）

#define _CRT_SECURE_NO_WARNINGS 1
#include 

using namespace std;

#define int long long
int m, n;
const int N = 2e5 + 10, inf = 3e9;

struct node
{
	int l, r;
	int key;
	int val;
	int cnt;
	int size;
} tr[N];

int root;
int idx;

void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

int get_node(int key)
{
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int& p)
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

void zag(int& p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}

void build()
{
    get_node(-inf), get_node(inf);
    root = 1, tr[1].r = 2;
    pushup(root);

    if (tr[1].val < tr[2].val) zag(root);
}

void insert(int& p, int key)
{
    if (!p) p = get_node(key);
    else if (tr[p].key == key) ++tr[p].cnt;
    else if (tr[p].key > key)
    {
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else
    {
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

int get_k_by_r(int p, int rank)
{
    if (!p) return inf;
    if (tr[tr[p].l].size >= rank) return get_k_by_r(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_k_by_r(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int a[N];
int op[N];
int st[N];

inline void add(int v)
{
    insert(root, v);
}

inline int get(int rank)
{
    return get_k_by_r(root, rank + 1);
}

signed main()
{
    build();

	int T = 1; //cin >> T;

	while (T--)
	{
		cin >> m >> n;
		for (int i = 1; i <= m; ++i) scanf("%lld", &a[i]);

		for (int i = 1; i <= n; ++i)
		{
			scanf("%lld", &op[i]), st[op[i]] ++;
		}

		int idx = 0;
		
		for (int i = 1; i <= m; ++i)
		{
			add(a[i]);
			while (st[i])
			{
				++idx;
				printf("%dn", get(idx));
				st[i]--;
			}
		}
	}

	return 0;
}