C++ の multiset を用い、最小値・最大値の取得と更新を問題文通りに行うことで解くことができます。

tatyam さんによる Python の SortedSet を用いることでも解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, Q;
	cin >> N >> Q;
	multiset<long> s;
	for (int i = 0; i < N; i++) {
		long A;
		cin >> A;
		s.insert(A);
	}
	for (int i = 0; i < Q; i++) {
		int T, R;
		long X;
		cin >> T >> X >> R;
		if (R) continue;
		auto it = (T == 1 ? prev(s.end()) : s.begin());
		s.erase(it);
		s.insert(X);
	}
	long ans = 0;
	for (long x : s) ans += x;
	cout << ans << '\n';
}