Submission #70836694

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
template <typename T>
using vc = vector<T>;
using ll = long long;

using PQ_max = priority_queue<int>;
using PQ_min = priority_queue<int, vector<int>, greater<int>>;

template <typename PQ>
struct Removable_Queue {
  PQ que, rm_que;
  int cnt = 0;
  ll sum = 0;

  bool empty() { return cnt == 0; }
  int top() {
    normalize();
    return que.top();
  }

  void push(int x) {
    que.push(x);
    cnt += 1, sum += x;
  }
  void pop(int x) {
    rm_que.push(x);
    cnt -= 1, sum -= x;
  }
  void pop() {
    normalize();
    cnt -= 1, sum -= que.top();
    que.pop();
  }

 private:
  void normalize() {
    while (!rm_que.empty() && rm_que.top() == que.top()) {
      rm_que.pop(), que.pop();
    }
  }
};

// total time complexity: sum((Q + sum_i |K_i-K_{i+1}|)log Q)
struct PartitionSum {
  Removable_Queue<PQ_max> que_l;
  Removable_Queue<PQ_min> que_r;
  void insert(int x) {
    if (que_l.empty() || que_l.top() < x) {
      que_r.push(x);
    } else {
      que_l.push(x);
    }
  }
  void erase(int x) {
    if (que_l.empty() || que_l.top() < x) {
      que_r.pop(x);
    } else {
      que_l.pop(x);
    }
  }
  pair<ll, ll> get_sum(int K) {
    assert(0 <= K && K <= que_l.cnt + que_r.cnt);
    while (que_l.cnt < K) {
      que_l.push(que_r.top()), que_r.pop();
    }
    while (que_l.cnt > K) {
      que_r.push(que_l.top()), que_l.pop();
    }
    return {que_l.sum, que_r.sum};
  }
};

void solve() {
  int N, M, Q;
  cin >> N >> M >> Q;
  vc<int> A(N + M), I(Q), X(Q);
  for (int i = 0; i < N + M; ++i) cin >> A[i];

  PartitionSum S1, S2;
  for (int x : A) S1.insert(x), S2.insert(x);

  for (int q = 0; q < Q; ++q) {
    int t, i, x;
    cin >> t >> i >> x;
    i = (t == 1 ? i - 1 : i - 1 + N);
    S1.erase(A[i]), S2.erase(A[i]);
    A[i] = x;
    S1.insert(A[i]), S2.insert(A[i]);
    auto [a, b] = S1.get_sum(N / 2);
    auto [c, d] = S2.get_sum(N / 2 + M);
    assert(a + b == c + d);
    ll ans = a + d;
    cout << ans << "\n";
  }
}

signed main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  solve();
}

Submission Info

Judge Result