中位数题解（整活）
题目描述
思路分析
这道题思路很多，比如说堆，平衡树，但还有一种比较简单的做法
主席树！！！
没错，静态区间第k小，这不纯纯主席树板子吗
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int cnt;
int n,m,a[N],b[N],root[N];
struct tree{
int l,r,sum;
}pst[N<<5];
int update(int pre,int pl,int pr,int x){
int rt=++cnt;
pst[rt].l=pst[pre].l;
pst[rt].r=pst[pre].r;
pst[rt].sum=pst[pre].sum+1;
int mid=(pl+pr)>>1;
if(pl<pr){
if(x<=mid) pst[rt].l=update(pst[pre].l,pl,mid,x);
else pst[rt].r=update(pst[pre].r,mid+1,pr,x);
}
return rt;
}
int query(int l,int r,int pl,int pr,int k){
if(pl==pr) return pl;
int x=pst[pst[r].l].sum-pst[pst[l].l].sum;
int mid=(pl+pr)>>1;
if(k<=x) return query(pst[l].l,pst[r].l,pl,mid,k);
else return query(pst[l].r,pst[r].r,mid+1,pr,k-x);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) {cin>>a[i];b[i]=a[i];}
sort(b+1,b+n+1);
int size=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){//1~i
int x=lower_bound(b+1,b+size+1,a[i])-b;
root[i]=update(root[i-1],1,size,x);
}
for(int i=1;2*i-1<=n;i+=1){
cout<<b[query(root[0],root[2*i-1],1,size,i)]<<endl;
}
return 0;
}