Running Median(离散+权值线段树)

题目：

往一个空序列加个数。当序列中数的个数为奇数个时，记录此时序列排序后的中位数。输出所有中位数。

做法：

看到中位数，第一时间想到权值线段树。所以我们先将所有数读进来离线处理。
先将所有数离散化，便与用线段树维护。
然后一个一个数加到序列中，线段树该数字出现的次数+1。奇数个数时，线段树上查询第小的数，这就是我们需要的中位数。
然后按题目要求输出就行了。

代码：

#include <bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e4 + 7;
int n, m, a[N];
vector<int> v, ans;
int T[N<<2];
int get(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void update(int pos, int l, int r, int rt){
    if (l == r){
        T[rt]++; return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) update(pos, l, mid, lson);
    else update(pos, mid+1, r, rson);
    T[rt] = T[lson]+T[rson];
}
int query(int k, int l, int r, int rt){
    if (l == r) return l;
    int mid = (l+r) >> 1;
    if (k <= T[lson]) return query(k, l, mid, lson);
    else return query(k-T[lson], mid+1, r, rson);
}
int main(void){
    IOS;
    int Te, t; cin >> Te;
    while (Te--){
        cin >> t >> n;
        v.clear(); ans.clear();
        memset(T, 0, sizeof T);
        for (int i = 1; i <= n; ++i){
            cin >> a[i];
            v.push_back(a[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        m = v.size();
        for (int i = 1; i <= n; i++){
            update(get(a[i]), 1, m, 1);
            if (i%2 == 1){
                int t = query(i/2+1, 1, m, 1);
                ans.push_back(v[t-1]);
            }
        }
        cout << t << ' ' << ans.size() << endl;
        for (int i = 0; i < ans.size(); ++i){
            if (i && i%10 == 0) cout << endl;
            cout << ans[i] << ' ';
        }
        cout << endl;
    }
    return 0;
}