题目描述
给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[2], …, A[2k - 1]的中位数。[color=red]即[/color]前1，3，5，……个数的中位数。
输入输出格式
输入格式：
输入文件median.in的第1行为一个正整数N，表示了序列长度。
第2行包含N个非负整数A[i] (A[i] ≤ 10^9)。
输出格式：
输出文件median.out包含(N + 1) / 2行，第i行为A[1], A[2], …, A[2i – 1]的中位数。
输入输出样例
输入样例#1：
7
1 3 5 7 9 11 6
输出样例#1：
1
3
5
6
说明
对于20%的数据，N ≤ 100；
对于40%的数据，N ≤ 3000；
对于100%的数据，N ≤ 100000。
用treap写中位数。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n;
struct node{
int lc,rc;
int rand,size;
int cnt,w;
}t[mxn];
int nct=,rot=;
void update(int rt){
t[rt].size=t[t[rt].lc].size+t[t[rt].rc].size+t[rt].cnt;
return;
}
void rturn(int &rt){
int tmp=t[rt].lc;
t[rt].lc=t[tmp].rc;
t[tmp].rc=rt;
update(rt);update(tmp);
rt=tmp;
return;
}
void lturn(int &rt){
int tmp=t[rt].rc;
t[rt].rc=t[tmp].lc;
t[tmp].lc=rt;
update(rt);update(tmp);
rt=tmp;
return;
}
void add(int &rt,int v){
if(!rt){
rt=++nct;
t[rt].w=v;
t[rt].cnt=;
t[rt].rand=rand();
t[rt].size=;
t[rt].lc=t[rt].rc=;
return;
}
t[rt].size++;
if(t[rt].w==v) t[rt].cnt++;
else if(v<t[rt].w){
add(t[rt].lc,v);
if(t[rt].rand>t[t[rt].lc].rand)rturn(rt);
}
else {
add(t[rt].rc,v);
if(t[rt].rand>t[t[rt].rc].rand)lturn(rt);
}
return;
}
int query(int rt,int k){
if(k<=t[t[rt].lc].size)return query(t[rt].lc,k);
if(k>t[t[rt].lc].size+t[rt].cnt)return query(t[rt].rc,k-t[t[rt].lc].size-t[rt].cnt);
return t[rt].w;
}
int main(){
n=read();
int i,j,x;
srand(n+);
for(i=;i<=n;i++){
x=read();
add(rot,x);
if(i&)printf("%d\n",query(rot,(i+)/));
}
return ;
}