简要题意：
给定一个长度为 (n) 的序列 (a)，求 (a_1) ~ (a_x) 的中位数。（(1 leq x leq n) 且 (x) 为奇数）
附注：中位数的定义：排序后位于最中间的数。如果长度为偶数则是最中间两个数的平均值。
(n leq 10^5) , (a_i leq 10^9).
这个题水不水，就看你怎么考虑了。
其实这个题不用高大上的数据结构，只需要模拟。
维护一个容器 (v)，逐渐加入 (a) 的元素，保证有序性。
每次都要加入一个元素，这是 插入排序 的原理，即二分找到该元素的位置，然后插入。(mathcal{O}(log n)).
但是我们需要选定的容器可以支持 快速插入，显然 vector 可以胜任，并且我们不用手写二分，可以用 upper_bound 来实现。
时间复杂度：(mathcal{O}(n log n)).
实际得分：(100pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
inline int read(){char ch=getchar(); int f=1; while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}
int n;
vector<int> v;
int main() {
n=read(); for(int i=1,x;i<=n;i++) {
x=read();
v.insert(upper_bound(v.begin(),v.end(),x),x); //找到位置并插入
if(i&1) printf("%d
",v[i>>1]); //中位数
}
return 0;
}