看到各路dalao用平衡树的做法，表示本人不才，并不会。
然而我会优先队列_huaji_，并且发现用堆解题的dalao们并没有基于在线的做法
于是我的showtime到了
评测结果：https://www.luogu.org/record/show?rid=4645103
先讲一下思路：
题干所描述的** i **的实际值并不重要，他只是作为堆的一个位置
当然如果你暴力模拟的话肯定会超时
为此我们考虑维护两个堆，一个是大根堆，一个是小根堆，且满足小根堆中的数比大根堆中的数大
用bool变量flag来表示当前所操作的是大根堆还是小根堆
首先是ADD(x)，按flag和x分为四种情况
然后是GET，按flag分为两种情况
具体操作见以下代码：
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<algorithm>
#pragma GCC optimize(3)//STL必带
using namespace std;
#define ll long long
const int maxn=2e5+10;
const int INF=0x7fffffff;
inline void read(int&x){//卡常的输入
int data=0,w=1;
char ch=getchar();
while(ch!='-'&&!isdigit(ch))
ch=getchar();
if(ch=='-')
w=-1,ch=getchar();
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
x=data*w;
}
void write(int x){//卡常的输出
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar('0'+x%10);
}
int a[maxn],u[maxn]={0};
priority_queue <int,vector<int>,less<int> > lrh;//大根堆，large root heap
priority_queue <int,vector<int>,greater<int> > srh;//小根堆，small root heap
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int m,n;
read(m);read(n);
for(int i=1;i<=m;++i)
read(a[i]);
int t;
for(int i=1;i<=n;++i){
read(t);
++u[t];
}
/*clog<<"u:"<<endl;
for(int i=1;i<=m;++i)
clog<<i<<" "<<u[i]<<endl;
clog<<"uend"<<endl;*/
bool flag=1;
srh.push(INF); //这个细节很重要，INF的值对此题没有影响，但是如果不加对第一个数的操作会RE的
#define x a[i]
#define y u[i]
for(int i=1;i<=m;++i){
if(flag)//ADD(x)
if(x<srh.top()){
lrh.push(x);
flag=0;
}
else
srh.push(x);
else
if(x<lrh.top()){//这一步是ADD的精华所在，对两个对做了等价变换
srh.push(lrh.top());//i值前移，因而大根堆要把最大数给小根堆
lrh.pop();
lrh.push(x);
}
else
srh.push(x);
while(y--){//GET
// clog<<"once in "<<i<<endl;
if(flag){//这一步是GET的精华所在，对两个对做了等价变换
write(srh.top());putchar('\n');
lrh.push(srh.top());//i值后移，因而小根堆要把最小数给大根堆
srh.pop();
}
else{
write(lrh.top());putchar('\n');
flag=1;
}
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}