@[Canthy_zy](/user/797187) 直接使用平衡树就可以了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1000;
#define ls(x) l_son[x]
#define rs(x) r_son[x]
int rt;
struct FHQ{
int l_son[N],r_son[N],dat[N],size[N];
int number[N],tot;
int make_new(int x){
size[++tot]=1;
dat[tot]=rand();
l_son[tot]=r_son[tot]=0;
number[tot]=x;
return tot;
}
#define maintain(x) size[x]=size[ls(x)]+size[rs(x)]+1
void split(int u,int &x,int &y,int val){
if(!u)return x=y=0,void();
if(number[u]<=val)x=u,split(rs(u),rs(u),y,val);
else y=u,split(ls(u),x,ls(u),val);
maintain(u);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(dat[x]<=dat[y]){
rs(x)=merge(rs(x),y);
maintain(x);
return x;
}
ls(y)=merge(x,ls(y));
maintain(y);
return y;
}
void ins(int x){
int l,r;
split(rt,l,r,x);
rt=merge(merge(l,make_new(x)),r);
}
int kth(int u,int k){
int Size=size[ls(u)]+1;
if(Size==k)return number[u];
if(Size<k)return kth(rs(u),k-Size);
return kth(ls(u),k);
}
}fhq;
int n;
int x;
int main(){
srand(time(0));
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
fhq.ins(x);
if(i%2==1){
cout<<fhq.kth(rt,(i+1)/2)<<'\n';
}
}
return 0;
}
```
by Zhangxm214 @ 2024-02-19 21:22:17
@[Zhangxm214](/user/1268594) 收到,谢谢,我代码错误调出来了,此贴结
by Rorou @ 2024-02-20 22:32:59