题目描述
给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[3], …, A[2k - 1]的中位数。即前1，3，5，……个数的中位数。
输入输出格式
输入格式：
输入文件median.in的第1行为一个正整数N，表示了序列长度。
第2行包含N个非负整数A[i] (A[i] ≤ 10^9)。
输出格式：
输出文件median.out包含(N + 1) / 2行，第i行为A[1], A[3], …, A[2i – 1]的中位数。
输入输出样例
说明
对于20%的数据，N ≤ 100；
对于40%的数据，N ≤ 3000；
对于100%的数据，N ≤ 100000。
/* 将a数组去重后存在b数组里，用b数组的大小建树。 用树的l作为数字，num记录这个数出现的次数， 则 更新时，找到a在b数组中的位置，让此位置的数++，表示这个数出现了一次 查询的时候，输出第i/2+1个数，则让x=i/2+1， 如果root的左儿子的num>=x，则说明要找的数在左子树里，否则在右子树里， 如果是去右子树里找，则让x-=tree[root<<1].num，因为我们在右子树里要找的是第x-=tree[root<<1].num个。 */ #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5; int n; int a[N],b[N]; struct Tree { int l,r,mid; int num; }tree[N<<2]; int read() { char c=getchar();int num=0; for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num; } void build(int root,int l,int r) { tree[root].l=l,tree[root].r=r,tree[root].mid=l+r>>1; if(l==r) return; build(root<<1,l,tree[root].mid); build(root<<1|1,tree[root].mid+1,r); } void update(int root,int x) { ++tree[root].num; if(tree[root].l==tree[root].r) return; if(x<=tree[root].mid) update(root<<1,x); else update(root<<1|1,x); } int query(int root,int num) { if(tree[root].l==tree[root].r) return tree[root].l; if(num<=tree[root<<1].num) return(query(root<<1,num)); else return(query(root<<1|1,num-tree[root<<1].num)); } int main() { n=read(); for(int i=1;i<=n;++i) a[i]=read(),b[i]=a[i]; sort(b+1,b+n+1); int bound=unique(b+1,b+n+1)-b; build(1,1,n); for(int i=1;i<=n;++i) { int pos=lower_bound(b+1,b+bound+1,a[i])-b; update(1,pos); if(i%2) printf("%d ",b[query(1,i/2+1)]); } return 0; }