Let \(S\) be the multiset of the integers written on the blackboard. Given \(Q\) insertion queries into \(S\), you are asked to find the median of \(S\) after each of them.

Here, consider a partition of \(S\) into two multisets \(S_1\) and \(S_2\) such that:

• \(|S_1|-|S_2|\) is \(0\) or \(1\).
• \(x \geq y\) for all \(x \in S_1\) and \(y\in S_2\).

Intuitively, we want to partition \(S\) into the large half \(S_1\) and small half \(S_2\). (If \(|S|\) is odd, \(S_1\) will have one more element.)

For this partition, we see that the median of \(S\) equals the minimum value of \(S_1\).

Also, a query inserting \(x\) into \(X\) can be processed by modifying \(S_1\) and \(S_2\) as follows:

• If \(x \ge \min S_1\), insert \(x\) to \(S_1\); otherwise, insert \(x\) to \(S_2\). (Now it remains that \(x \geq y\) for all \(x \in S_1\) and \(y\in S_2\), but \(|S_1|-|S_2| \in \lbrace 0,1\rbrace\) may no longer be satisfied.)
• If \(|S_1| > |S_2|+1\) remove one instance of \(\min S_1\) from \(S_1\), and insert it to \(S_2\) instead.
• If \(|S_2| > |S_1|+1\) remove one instance of \(\max S_2\) from \(S_2\), and insert it to \(S_1\) instead.

These operations can be easily implemented by managing \(S_1\) and \(S_2\) in a priority queue.

The problem can be solved by properly implementing the algorithm above. The complexity is \(O(Q \log Q)\).

Sample code (C++)

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int x;
	cin >> x;
	priority_queue<int> L;
	priority_queue<int, vector<int>, greater<int>> R;
	L.push(x);
	auto add = [&](int val) {
		if (val <= L.top()) {
			L.push(val);
		} else {
			R.push(val);
		}
		if (L.size() < R.size() + 1) {
			L.push(R.top());
			R.pop();
		}
		if (L.size() > R.size() + 1) {
			R.push(L.top());
			L.pop();
		}
	};
	int Q;
	cin >> Q;
	while (Q--) {
		int a, b;
		cin >> a >> b;
		add(a), add(b);
		cout << L.top() << '\n';
	}
	return 0;
}

Sample code (Python3)

import sys

input = sys.stdin.readline
from heapq import heappush, heappop

L = [-int(input())]
R = []


def add(x):
    if x <= -L[0]:
        heappush(L, -x)
    else:
        heappush(R, x)

    if len(L) < len(R) + 1:
        heappush(L, -heappop(R))
    if len(L) > len(R) + 1:
        heappush(R, -heappop(L))


for _ in range(int(input())):
    a, b = map(int, input().split())
    add(a), add(b)
    print(-L[0])