昨晚恶补了一下二叉堆的内容
然后就找了几个二叉堆的题来做awa
然后发现用二叉堆做这题复杂度是O（nlogn）
但是有O（n）的解法
（某大佬这么说）
思路大概就是：
利用一个大根堆一个小根堆来维护第k小，并没有强制在线
不强制在线，所以我们直接读入所有元素，枚举询问，因为
要询问第k小，所以把前面的第k个元素都放进大根堆里面，
然后如果元素数量大于k，就把堆顶弹掉放到小根堆里面，
使大根堆的元素严格等于k，这样这次询问的结果就是小根
堆的堆顶了（前面k-1小的元素都在大根堆里面了）
记得在完成这次询问后重新把小根堆的堆顶放到大根堆里面就好
详见代码：
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#define ll long long
#define inf 1<<30
#define il inline
#define in1(a) read(a)
il int max(int x,int y) {
return x>y?x:y;
}
il int min(int x,int y) {
return x<y?x:y;
}
il int abs(int x) {
return x>?x:-x;
}
il void swap(int &x,int &y) {
int t=x;
x=y,y=t;
}
il void readl(ll &x) {
x=;
ll f=;
char c=getchar();
while(c<''||c>'') {
if(c=='-')f=-f;
c=getchar();
}
while(c>=''&&c<='') {
x=x*+c-'';
c=getchar();
}
x*=f;
}
il void read(int &x) {
x=;
int f=;
char c=getchar();
while(c<''||c>'') {
if(c=='-')f=-f;
c=getchar();
}
while(c>=''&&c<='') {
x=x*+c-'';
c=getchar();
}
x*=f;
}
//上边大部分并没有用
using namespace std;
#define N 200010
priority_queue<int,vector<int>,greater<int> > q;
priority_queue<int> q1;
int n,m,a[N],b[N];
int main() {
in1(n),in1(m);
for(int i=; i<=n; i++)in1(a[i]);
for(int i=; i<=m; i++)in1(b[i]);
int i=;
for(int j=; j<=m; j++) {
for(; i<=b[j]; i++) {
q1.push(a[i]);
if(q1.size()==j)q.push(q1.top()),q1.pop();
}
printf("%d\n",q.top());
q1.push(q.top());
q.pop();
}
return ;
}