数据流动态中位数查询器

#include <bits/stdc++.h>
using namespace std;

// 数据流动态中位数查询器
class MediumFinder {
public:
  priority_queue<int> small;                          // 大根堆
  priority_queue<int, vector<int>, greater<int>> large; // 小根堆

  void make_balance() {
    if (small.size() >= large.size() + 2) {
      int top = small.top();
      small.pop();
      large.push(top);
    } else if (small.size() < large.size()) {
      int top = large.top();
      large.pop();
      small.push(top);
    }
  }

  void push(int item) {
    if (small.empty() || item <= small.top())
      small.push(item);
    else
      large.push(item);

    make_balance();
  }

  double get_medium() {
    if (small.size() == large.size()) {
      return (small.top() + large.top()) / 2.0;
    } else {
      return small.top();
    }
  }
};

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n - 1);
    for (int i = 0; i < n; i++)
      cin >> a[i];
    for (int i = 0; i < n - 1; i++)
      cin >> b[i];

    // 逆向思考
    // 由于b中最小值为1，所以不会删除a[0]，所以到最后的中位数必然是a[0]
    vector<double> mediums = {(double)a[0]};
    MediumFinder medium_finder;
    medium_finder.push(a[0]);
    for (int i = b.size() - 1; i >= 0; i--) {
      medium_finder.push(a[b[i]]);
      mediums.push_back(medium_finder.get_medium());
    }

    reverse(mediums.begin(), mediums.end());
    for(auto m : mediums) {
        if (m - int(m)) printf("%.1f ", m);
        else printf("%d ", int(m));
    }
    cout<<endl;
  }
  return 0;
}