题解
方法一
无脑平衡树。
方法二
堆的神奇操作。
发现这个求第$k$小$k$是递增的，所以可以维护一个大根堆和一个小根堆，然后
在其中一个堆上维护前$k$个数，另一个堆上维护剩下的数，
这样只要关注第$k$个数是什么即可，而不需要管在他前面的或者在他后面的是不是有序的。
所以操作就很简单了，$k$加$1$的时候从某个堆弹一个走就行了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
int h[200005]={0},size=0,n,m,k[200005];
priority_queue<int> pq;
//pq下<pq顶<h顶<h底
void up(int s){
int at,tmp=h[s];
while(s>0){
at=(s-1)/2;
if(h[at]<=tmp)break;
h[s]=h[at],s=at;
}
h[s]=tmp;
}
void down(int s,int e){
int lch,rch,tmp=h[s];
while(l(s)<e){
lch=l(s),rch=r(s);
if(rch<e&&h[rch]<h[lch])
lch=rch;
if(tmp<=h[lch])break;
h[s]=h[lch],s=lch;
}
h[s]=tmp;
}
int main(){
scanf("%d%d",&m,&n);
int i,j,at;
for(i=0;i<m;i++)
scanf("%d",&k[i]);
pq.push(k[0]);
for(i=0,j=1;i<n;i++){
scanf("%d",&at);
while(j<at){
if(pq.top()>k[j]){
h[size++]=pq.top(),pq.pop();
pq.push(k[j]),up(size-1);
}else
h[size++]=k[j],up(size-1);
j++;
}
printf("%d\n",pq.top());
if(!size)h[size++]=k[j++];
pq.push(h[0]),h[0]=h[--size],down(0,size);
}
return 0;
}