题意

求给定数组的动态中位数（时的中位数)。

分析

求中位数，不就相当于求当前数列的第 大吗？
于是自然地想到了权值线段树。
权值线段树可以在 内找到第 大值。
不过在此题中，由于空间限制很紧，不能用动态开点，而需要先离散化。

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define N 10000
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int a[N], b[N], sum[N * 2];
void update(int l, int r, int rt, int p, int c){
    sum[rt] += c;
    if(l == r) return;
    int m = l + r >> 1;
    if(p <= m) update(lson, p, c);
    else update(rson, p, c);
}
int find(int l, int r, int rt, int x){
    if(l == r) return l;
    int m = l + r >> 1;
    if(x <= sum[rt << 1]) return find(lson, x);
    return find(rson, x - sum[rt << 1]);
}
int main(){
    int i, j, T, n, m, tot = 0, ans;
    T = read();
    while(T--){
        memset(sum, 0, sizeof(sum));
        j = read(); n = read();
        printf("%d %d\n", j, (n + 1) / 2);
        for(i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
        sort(b + 1, b + n + 1);
        m = unique(b + 1, b + n + 1) - b - 1;
        for(i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
        tot = 0;
        for(i = 1; i <= n; i++){
            update(1, m, 1, a[i], 1);
            j = (i + 1) / 2;
            if(i % 2){
                tot++;
                ans = b[find(1, m, 1, j)];
                printf("%d ", ans);
                if(tot == 10 && i < n) tot = 0, printf("\n");
            }
        }
        printf("\n");
    }
    return 0;
}