维护一个大根堆，维护一个小根堆，大根堆有k个数，堆首就是第k大的，不会写堆，这里用优先队列来实现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#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int n,m;
int k=0;
long long a[299999];
int f[299999];
priority_queue <long long> qued;
priority_queue <long long> quex;
void work(){
k++;
qued.push(-quex.top());
quex.pop();
printf("%d\n",qued.top());
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
scanf("%lld",&a[i]);
for(int j=1;j<=n;j++){
long long x;
scanf("%lld",&x);
f[x]++;
}
//for(int i=1;i<=m;i++) printf("%d",f[i]);
for(int i=1;i<=m;i++){
long long x=a[i];
if(k==0) quex.push(-x);
else if(qued.top()>x)
{
quex.push(-qued.top());
qued.pop();
qued.push(x);
}
else quex.push(-x);
while(f[i]){
work();f[i]--;
}
}
}