ARC210B

liuyongtao · 2025-11-17 15:27:27 · 题解

首先，保留在 X 中的元素一定是 A, B 组成的多重集 S（|S| = n + m）按大小排名前与后 \frac n 2 的元素。证明考虑如下：

2. 对于一个在 S 中排名为 k 且 k \le\frac n 2 的元素，它任意时刻在 X 中的排名一定不大于 k。

结合 1, 2 得知该元素永远不会成为中位数（排名后 \frac n 2 同理），故而 X 完全由这些元素组成。

于是我们要维护多重集 S，支持元素替换与查询排名前（或后）\frac n 2 的元素的和。

笔者认为最简洁的实现是开三个 multiset，分别维护排名前 \frac n 2、后 \frac n 2 及其余的元素。每次将新元素插入中间的 multiset 后再调整 size 与排名关系。

:::success[code]

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

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

  int n, m, q;
  cin >> n >> m >> q;
  vector<int> a(n + m + 1);
  multiset<int> S[3];
  for (int i = 1; i <= n + m; i++) {
    cin >> a[i];
    S[1].insert(a[i]);
  }
  i64 sum = 0;
  for (int i = 0; i < n / 2; i++) {
    auto it = S[1].begin(), it2 = --S[1].end();
    S[0].insert(*it), S[2].insert(*it2);
    sum += *it + *it2;
    S[1].erase(it), S[1].erase(it2);
  }
  while (q--) {
    int t, i, x;
    cin >> t >> i >> x;
    if (t == 2) i += n;
    for (int j : {0, 1, 2}) {
      auto it = S[j].find(a[i]);
      if (it != S[j].end()) {
        if (j != 1) sum -= a[i];
        S[j].erase(it);
        break;
      }
    }
    a[i] = x;
    S[1].insert(x);
    if ((int)S[0].size() < n / 2) {
      auto it = S[1].begin();
      S[0].insert(*it);
      sum += *it;
      S[1].erase(it);
    } else if ((int)S[2].size() < n / 2) {
      auto it = --S[1].end();
      S[2].insert(*it);
      sum += *it;
      S[1].erase(it);
    }
    auto it0 = --S[0].end(), it10 = S[1].begin();
    auto it11 = --S[1].end(), it2 = S[2].begin();
    if (*it0 > *it10) {
      S[0].insert(*it10), S[1].insert(*it0);
      sum += -*it0 + *it10;
      S[0].erase(it0), S[1].erase(it10);
    } else if (*it2 < *it11) {
      S[2].insert(*it11), S[1].insert(*it2);
      sum += -*it2 + *it11;
      S[2].erase(it2), S[1].erase(it11);
    }
    cout << sum << endl;
  }
}

:::