ARC210B

首先，保留在

X

中的元素一定是

A, B

组成的多重集

S

（

|S| = n + m

）按大小排名前与后

\frac n 2

的元素。证明考虑如下：

$|X|$ 在每次操作后都为 $n$ ；
对于一个在 $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 与排名关系。

code

CPP

#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;
  }
}

文章操作

相关推荐

评论

ARC210B