O(W+q) 堆（离线）

n_ni · 2026-07-30 16:56:56 · 算法·理论

需要实现的操作：

1. 将 x 插入集合中。
2. 查询集合元素的最小值。
3. 将最小值从集合中删除。

考虑把插入操作单独列出，记为序列 a，其中 a_i 表示第 i 个插入的数的值。记 m_i 表示第 i 次操作后堆中最小值。

此时对 a_i 升序排序（如果用 sort 就会导致复杂度变成 O(q\log q)，与正常堆复杂度相等，所以这里使用桶排序）。

这时侯 a_i 在某次操作后是最小值的条件为：

• 此时对于 1 \le j < i，a_j 不在堆中。

因为删除操作所删除的的是当前的最小值，查询操作只和当前最小值有关，所以当堆顶的值小于 a_i 时所有操作都与 a_i 无关。于是可以先求出哪些时刻堆中最小值小于等于 a_i，然后从 a_i 被加入的操作开始向后走，若 m_j<a_i 则直接跳过，否则令 m_j \gets a_i，直到 a_i 被弹出。

但是上面的做法是 O(W+q^2) 的，考虑优化。

发现 m_j 被覆盖之后就不会再被覆盖，相当于直接从操作序列中被删除了。所以考虑用链表维护这一操作。此时每个 m_j 只会被覆盖一次，加上前面 O(W) 的桶排，复杂度为 O(W+q)。

只适合 W 较小的场合。