【每日一题】Running Median

Solution

权值线段树求区间第k小裸题。
先对给定的数列进行离散化（或动态开点），然后逐个插入线段树中，当下标为奇数时，利用线段树找到第小的数即可。

题目难度主要在读题上。

总复杂度

Code

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

using ll = long long;

struct Tree {
  int _n, sum[1 << 15];
  void init(int n) {
    _n = 1;
    while (_n < n) {
      _n <<= 1;
    }
    for (int i = 0; i < (_n << 1); i++) {
      sum[i] = 0;
    }
  }
  void upd(int at, int d) {
    at += _n, sum[at] += d;
    while (at > 1) {
      at /= 2, sum[at] = sum[at * 2] + sum[at * 2 + 1];
    }
  }
  int query(int k, int i, int l, int r) {
    if (l + 1 == r) {
      return l;
    }
    int mid = (l + r) / 2;
    if (sum[i * 2] >= k) {
      return query(k, i * 2, l, mid);
    } else {
      return query(k - sum[i * 2], i * 2 + 1, mid, r);
    }
  }
  int query(int k) {
    return query(k, 1, 0, _n);
  }
} tree;

int a[10004], b[10004];

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    int tc, n;
    cin >> tc >> n;
    for (int i = 0; i < n; i++) {
      cin >> a[i], b[i] = a[i];
    }
    sort(b, b + n);
    int m = unique(b, b + n) - b;
    for (int i = 0; i < n; i++) {
      a[i] = lower_bound(b, b + m, a[i]) - b;
    }
    tree.init(m);
    cout << tc << " " << (n + 1) / 2 << "\n";
    for (int i = 0; i < n; i++) {
      tree.upd(a[i], 1);
      if (~i & 1) {
        int id = i / 2;
        cout << b[tree.query(i / 2 + 1)] << " \n"[(id + 1 == (n + 1) / 2) || ((id + 1) % 10 == 0)];
      }
    }
  }
}