既然要求中位数,等价于求排名为 $(n + 1) \div 2$ 的数,明显可以使用平衡树
这里使用的是 Splay ,代码如下:
#include <cstdio>
#include <cstring>
#include <cctype>
inline int read() {
int num = 0 ,f = 1; char c = getchar();
while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
return num * f;
}
inline int max(int a ,int b) {return a > b ? a : b;}
inline int min(int a ,int b) {return a < b ? a : b;}
const int N = 10005 ,INF = 0x3f3f3f3f;
struct Splay {
struct node {
int ch[2] ,fa ,size ,val ,cnt;
node () : fa(0) ,size(0) ,val(0) ,cnt(0) {ch[0] = ch[1] = 0;}
}t[N]; int tot ,root;
Splay() : tot(0) ,root(0) {}
inline void clear() {
for (int i = 1; i <= tot; i++) t[i] = node();
tot = 0; root = 0;
}
inline void update(int now) {
t[now].size = t[t[now].ch[0]].size + t[t[now].ch[1]].size + t[now].cnt;
}
inline void rotate(int x) {
int y = t[x].fa ,z = t[y].fa ,k = t[y].ch[1] == x;
t[x].fa = z; t[z].ch[t[z].ch[1] == y] = x;
t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;
t[x].ch[k ^ 1] = y; t[y].fa = x;
update(y); update(x);
}
inline void splay(int x ,int goal) {
while (t[x].fa != goal) {
int y = t[x].fa ,z = t[y].fa;
if (z != goal)
if ((t[z].ch[1] == x) == (t[y].ch[1] == x)) rotate(y);
else rotate(x);
rotate(x);
}
if (goal == 0) root = x;
}
inline void insert(int val) {
int now = root ,fa = 0;
while (now && t[now].val != val) fa = now ,now = t[now].ch[val > t[now].val];
if (now) t[now].cnt++;
else {
now = ++tot;
t[now].val = val;
t[now].size = t[now].cnt = 1;
t[now].fa = fa;
t[fa].ch[val > t[fa].val] = now;
}
splay(now ,0);
}
inline int findval(int rank) {
if (rank < 1 || rank > t[root].size) return INF;
int now = root;
while (now) {
if (t[t[now].ch[0]].size >= rank) now = t[now].ch[0];
else if (t[t[now].ch[0]].size + t[now].cnt >= rank) return t[now].val;
else rank -= t[now].cnt + t[t[now].ch[0]].size ,now = t[now].ch[1];
}
return INF;
}
inline void build() {
insert(-INF); insert(INF);
}
}t;
int T ,n;
signed main() {
T = read();
for (int tptpt = 1; tptpt <= T; tptpt++) {
int useless = read() ,cnt = 0;
t.build();
n = read();
printf("%d %d\n" ,tptpt ,(n + 1) >> 1);
for (int i = 1; i <= n; i++) {
t.insert(read());
if (i % 2 == 1) printf("%d " ,t.findval(((i + 1) >> 1) + 1)) ,cnt++;
if (cnt == 10) puts("") ,cnt = 0;
}
t.clear();
}
return 0;
}