ABC127 F - Absolute Minima

https://atcoder.jp/contests/abc127/tasks/abc127_f

Maintain the first smallest half of a[i] and the second smallest half of a[i], call them L and R respectively. Then, the answer is sum(R)-sum(L) if L and R have the same number of elements.

To maintain them efficiently, we prepare two heaps, the one is a max-heap called L and the other is a min-heap called R. When given the input a[i] and b[i], we insert a[i] into both heaps, that is, do L.push(a[i]) and R.push(a[i]). After this operation, it might be L.top() > R.top(). If so, we swap them. After this, L.top() <= R.top() always holds. Note that L.top() <= R.top() implies L has the first smallest half of a[i] and R is also the same.

Since a[i] is counted doubly, the answer is a little different from the described above. It becomes (sum(R) - sum(L))/2. When L.top() > R.top(), two elements moves between L and R mutually. At this time, the (sum(R)-sum(L))/2 increases by x-y, where x and y are L.top() and R.top() respectively.

The following code is based on the explanation above. Clearly, we can use a balanced binary search tree or a binary indexed tree for solving this problem. BST and BIT appear in various situations. So it might be easier than the heap-based solution for experienced competitors.

By the way, as far as I know, two heap technique is written in "Cracking the Coding Interview." So it might be more well-known than many people think.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>

using namespace std;

using ll = long long;
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<class T> using maxheap = priority_queue<T, vector<T>, less<T>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int Q;
  cin >> Q;
  maxheap<ll> L;
  minheap<ll> R;
  ll ans = 0;
  while (Q--) {
    int type;
    cin >> type;
    if (type == 1) {
      ll a, b;
      cin >> a >> b;
      ans += b;
      L.push(a);
      R.push(a);
      if (L.top() > R.top()) {
        ll l = L.top(); L.pop();
        ll r = R.top(); R.pop();
        ans += l - r;
        L.push(r);
        R.push(l);
      }
    } else {
      cout << L.top() << ' ' << ans << '\n';
    }
  }
}