Solution

分析题意,要求我们求出每一个奇数长度前缀的中位数
对于每一个奇数长度前缀,设长度为len,求中位值其实就是求区间第(len + 1) / 2大
那么显然这就是一道求区间第k大的模板题了
我们直接上主席树,秒掉这个问题
这里简单介绍下主席树
主席树又叫可持久化线段树，它是基于线段树发展而来的一种数据结构。
给线段树增加一些历史点来维护历史数据，使得我们能在较短时间内查询历史数据。
主席树思想是每个位置都维护一个线段树，线段树的节点是值的范围。
然后第i个线段树中某个区间[x, y]维护的是，1-i中数字在[x, y]范围内的个数。
因此我们运用前缀和的思想,在主席树上二分递归求解即可求出区间第k大。
注意数据范围，需要先离散化。
时间复杂度大概是?

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e5 + 5;
const ll mod = 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int n, q, m, tot;
int a[N], t[N];
int T[N], lson[N * 50], rson[N * 50], c[N * 50];
void Init_hash(){
  for(int i = 1; i <= n; i++){
    t[i] = a[i];
  }
  sort(t + 1, t + 1 + n);
  m = unique(t + 1, t + 1 + n) - t - 1;
}
int Hash(int x){
  return lower_bound(t + 1, t + 1 + m, x) - t;
}
int build(int l, int r){
  int root = tot++;
  c[root] = 0;
  if(l != r){
    int mid = l + r >> 1;
    lson[root] = build(l, mid);
    rson[root] = build(mid + 1, r);
  }
  return root;
}
int Insert(int root, int pos, int val){
  int newroot = tot++, tmp = newroot;
  c[newroot] = c[root] + val;
  int l = 1, r = m;
  while(l < r){
    int mid = l + r >> 1;
    if(pos <= mid){
      lson[newroot] = tot++, rson[newroot] = rson[root];
      newroot = lson[newroot], root = lson[root];
      r = mid;
    }
    else {
      rson[newroot] = tot++, lson[newroot] = lson[root];
      newroot = rson[newroot], root = rson[root];
      l = mid + 1;
    }
    c[newroot] = c[root] + val;
  }
  return tmp;
}
int Query(int left_root, int right_root, int k){
  int l = 1, r = m;
  while(l < r){
    int mid = l + r >> 1;
    int tmp = c[lson[left_root]] - c[lson[right_root]];
    if(tmp >= k){
      r = mid;
      left_root = lson[left_root];
      right_root = lson[right_root];
    }
    else {
      l = mid + 1;
      k -= tmp;
      left_root = rson[left_root];
      right_root = rson[right_root];
    }
  }
  return l;
}
int main(){
  int Tcase;
  cin >> Tcase;
  int cas = 0;
  while(Tcase--){
    tot = 0;
    ++cas;
    int p;
    cin >> p;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    Init_hash();
    T[n + 1] = build(1, m);
    for(int i = n; i; i--){
      int pos = Hash(a[i]);
      T[i] = Insert(T[i + 1], pos, 1);
    }
    vector<int> v;
    for(int i = 1; i <= n; i += 2){
      v.push_back(t[Query(T[1], T[i + 1], (i + 1) / 2)]);
    }
    cout << cas << ' ' << v.size() << "\n";
    for(int i = 0; i < v.size(); i++){
      if(i && i % 10 == 0){
        cout << "\n";
      }
      cout << v[i] << " \n"[i == v.size() - 1];
    }
  }
  return 0;
}