摘要：
您可以使用称为top heap的东西，这是一种在线维护第n个最小logn的算法。但似乎其他平衡树也能解决这个问题。例如，一场排名很快的比赛？既然这出戏这么复杂，你为什么不用主席树呢？事实上，我们仍然需要旋转来保持平衡树的特性……第k个最小值的动态维护也可以通过各种平衡树来完成。顶部堆保持顶部堆只会持续扩展的状态非常方便。这里我们根据标题将其命名为“黑盒堆栈”：请注意，每次顶部堆栈扩展时，如果底部堆栈中有元素，它们将首先从底部堆栈中获得。
这道题是提高+省选-的难度，做出来的话对数据结构题目的理解会增加很多。
可以使用一种叫做对顶堆的东西，对顶堆是在线维护第n小的logn的算法。大概的思路是，假如我们要找的是第n小，我们就维护一个大小为n的（位于下方的）大顶堆，（位于上方的）小顶堆中每个元素都比大顶堆的大。在这道题中，n不变时每次有新的比他小的就把堆顶弹出到对顶（也就是小顶堆）的堆顶，每次n扩大的时候就从（上面的）小顶堆里取出堆顶放进大顶堆的堆顶……
但是看样子应该其他平衡树也是可以解决这个问题的。比如支持快速名次的splay？还有完全另一个维度复杂的主席树（区间第k大）。
这道题应该是对顶堆最简单了。但是明显是用别的数据结构更好，因为对顶堆的第n小只能慢慢变……这样真的不如splay……（当然啦！splay这么复杂，你怎么不用主席树呢？主席树还区间第k大呢？）
Pdalao说了一个，可以用BST来维护，每个节点维护左子树的名次，那么找k的时候就可以判断是进入左子树还是右子树了，陷入思考……其实还是要旋转来保持平衡树的特性……
真实的递归学习法，一个两个都不会。
动态维护第k小也可以交给各类平衡树去完成。 而且k还可以不断改。
对顶堆用来维护一种顶堆只会不断扩大的情形非常方便。和之前的动态求中位数一个道理。
这里我们根据题目命名为“黑匣子堆”：注意每次顶堆扩大时，假如底堆有元素则优先从底堆获取。
#include<bits/stdc++.h> using namespacestd; structBlack_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; inti; Black_Box_Heap(){i=0;} void add(intvalue){ 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(); } returnt; } }bbh; int a[200005]; intmain(){ intm,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++){ intu; scanf("%d",&u); while(u>=j){ bbh.add(a[j]); j++; } printf("%d ",bbh.get()); } }