洛谷 - P1801 - 黑匣子 - 对顶堆

这道题是提高+省选-的难度，做出来的话对数据结构题目的理解会增加很多。

可以使用一种叫做对顶堆的东西，对顶堆是在线维护第n小的logn的算法。大概的思路是，假如我们要找的是第n小，我们就维护一个大小为n的（位于下方的）大顶堆，（位于上方的）小顶堆中每个元素都比大顶堆的大。在这道题中，n不变时每次有新的比他小的就把堆顶弹出到对顶（也就是小顶堆）的堆顶，每次n扩大的时候就从（上面的）小顶堆里取出堆顶放进大顶堆的堆顶……

但是看样子应该其他平衡树也是可以解决这个问题的。比如支持快速名次的splay？还有完全另一个维度复杂的主席树（区间第k大）。

 

这道题应该是对顶堆最简单了。但是明显是用别的数据结构更好，因为对顶堆的第n小只能慢慢变……这样真的不如splay……（当然啦！splay这么复杂，你怎么不用主席树呢？主席树还区间第k大呢？）

Pdalao说了一个，可以用BST来维护，每个节点维护左子树的名次，那么找k的时候就可以判断是进入左子树还是右子树了，陷入思考……其实还是要旋转来保持平衡树的特性……

 

真实的递归学习法，一个两个都不会。

---

动态维护第k小也可以交给各类平衡树去完成。 而且k还可以不断改。

对顶堆用来维护一种顶堆只会不断扩大的情形非常方便。和之前的动态求中位数一个道理。

这里我们根据题目命名为“黑匣子堆”：注意每次顶堆扩大时，假如底堆有元素则优先从底堆获取。

#include<bits/stdc++.h>
using namespace std;

struct Black_Box_Heap{
    //top_heap has the min element,bottom heap has the max element

    priority_queue<int,vector<int>,less<int> > top_heap;
    priority_queue<int,vector<int>,greater<int> > bottom_heap;

    int i;

    Black_Box_Heap(){i=0;}

    void add(int value){
        if(top_heap.size()<=i){
            top_heap.push(value);
        }
        else{
            if(value<top_heap.top()){
                bottom_heap.push(top_heap.top());
                top_heap.pop();
                top_heap.push(value);
            }
            else{
                bottom_heap.push(value);
            }
        }
    }

    int get(){
        int t=top_heap.top();
        i++;
        while(top_heap.size()<=i&&!bottom_heap.empty()){
            top_heap.push(bottom_heap.top());
            bottom_heap.pop();
        }
        return t;
    }
}bbh;

int a[200005];

int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }

    int j=1;
    for(int i=1;i<=n;i++){
        int u;
        scanf("%d",&u);
        while(u>=j){
            bbh.add(a[j]);
            j++;
        }

        printf("%d\n",bbh.get());
    }
}