奶牛喝水(动态中位数)

AisDaeun 5 2023-12-02

奶牛喝水

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int arr[N], ptr[N], inv[N], Prev[N], Next[N], res[N], ans[N];
int read() {
	int x(0); char ch(getchar());
	for (; !isdigit(ch); ch = getchar());
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return x;
}
int getmid(int n) {
	for (int i = Next[0], cnt = 0; ~Next[i]; i = Next[i])
		if (++cnt == (n + 1) >> 1) return i;
}
//inv[i] 原序列中第i个数在排序后的序列中是第inv[i]个
//ptr[i] 排序后第i个数在原序列中是第ptr[i]个
void del(int x) {
	Next[Prev[x]] = Next[x];
	Prev[Next[x]] = Prev[x];
}
void solve() {
	int n = read();
	for (int i = 1; i <= n; i++) arr[i] = read(), ptr[i] = i;
	sort(ptr + 1, ptr + n + 1, [&] (int x, int y) {
		return arr[x] < arr[y];
	});
	for (int i = 1; i <= n; i++) inv[ptr[i]] = i;
	for (int i = 1; i <= n; i++) Prev[i] = i - 1, Next[i] = i + 1;
	Next[0] = 1, Prev[n + 1] = n, Next[n + 1] = -1;
	if ((n & 1) == 0) del(inv[n--]);
	int idx = (n + 1) >> 1, mid = getmid(n);
	for (int i = n; i > 1; i -= 2) {
		res[idx--] = arr[ptr[mid]];
		del(inv[i]), del(inv[i - 1]);
		int a = inv[i], b = inv[i - 1];
		if (a > b) swap(a, b);
		if (a >= mid) mid = Prev[mid];
		else if (b <= mid) mid = Next[mid];
	}
	res[idx--] = arr[ptr[Next[0]]];
	int cnt = 0;
	for (int i = 1; i <= (n + 1) >> 1; i++)
		if (ans[cnt] != res[i]) ans[++cnt] = res[i];
	printf("%d\n", cnt);
	for (int i = 1; i <= cnt; i++) printf("%d ", ans[i]);
	printf("\n");
}
int main() {
	int t = read();
	while (t--) solve();
}