树状数组 + 二分 动态维护树状数组 : $\mathcal O(n\log n)$
类似题 : Acwing 244. 谜一样的牛
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int id;
int n;
int a[N], w[N], cnt;
int tr[N];
int lowbit(int x) {
return x & -x;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void add(int x, int v) {
for (int i = x; i < N; i += lowbit(i)) tr[i] += v;
}
int find(int x) {
return lower_bound(w + 1, w + 1 + cnt, x) - w;
}
void solve() {
cin >> id >> n;
cout << id << ' ' << (n + 1) / 2 << "\n";
cnt = 0;
memset(w, 0, sizeof w);
memset(tr, 0, sizeof tr);
for (int i = 1; i <= n; i ++ ) cin >> a[i], w[ ++ cnt] = a[i];
sort(w + 1, w + 1 + cnt);
cnt = unique(w + 1, w + 1 + cnt) - w - 1;
int cur = 0;
for (int i = 1; i <= n; i ++ ) {
int k = find(a[i]);
add(k, 1);
if (i & 1) {
int l = 1, r = cnt;
while (l < r) {
int mid = (l + r) >> 1;
if (query(mid) >= (i + 1) / 2) r = mid;
else l = mid + 1;
}
cout << w[l] << ' ';
cur ++;
if (cur == 10) {
cout << "\n";
cur = 0;
}
}
}
if (((n + 1) / 2) % 10 != 0) cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T -- ) solve();
return 0;
}