\(\max(a_x + a_y, b_y + b_x)\) 的贡献形式不是独立的，并不好进行分析。考虑通过分类讨论将 \(\max\) 拆开。若令 \(h_i = a_i - b_i\)，\(h'_i = b_i - a_i\)，可以发现若 \(h_x \geqslant h'_y\) 取值则为 \(b_x + b_y\)，反之亦然。
注意到 \(h\) 本身自带一个一维偏序关系，于是放到数轴上用线段树维护，每个节点维护 \(a_x\)，\(a_y\)，\(b_x\)，\(b_y\) 的最小值，以及区间的答案。修改操作在线段树的叶子节点维护四个 std::multiset 即可。
const int N = 1e6;
const int INF = numeric_limits<int>::max();
int Q, opt[N + 100], cat[N + 100], a[N + 100], b[N + 100];
using MSET = multiset<ll>;
struct node {
ll mn[4], ans;
node() : ans(INF) {
for (int i = 0; i < 4; ++i) mn[i] = INF;
}
};
struct SegmentTree {
#define NODE int u, int l, int r
#define mid (((l) + (r)) / 2)
#define ls (u * 2)
#define rs (u * 2 + 1)
#define LC ls, l, mid
#define RC rs, mid + 1, r
#define SetAcc(id, i) (*leaves[id][i].begin())
const int __n;
vector<node> body;
vector<array<MSET, 4>> leaves;
void pullup(int u) {
body[u].ans = min({body[ls].mn[2] + body[rs].mn[0], body[ls].mn[1] + body[rs].mn[3], body[ls].ans, body[rs].ans});
for (int i = 0; i < 4; ++i) body[u].mn[i] = min(body[ls].mn[i], body[rs].mn[i]);
}
void upd(int pos, NODE) {
if (l == r) {
for (int i = 0; i < 4; ++i) body[u].mn[i] = SetAcc(l, i);
body[u].ans = min(SetAcc(l, 0) + SetAcc(l, 2), SetAcc(l, 1) + SetAcc(l, 3));
} else mid >= pos ? upd(pos, LC) : upd(pos, RC), pullup(u);
}
public:
void upd(int pos) {upd(pos,1,1,__n);}
int Ask() {return body[1].ans;}
SegmentTree(int n) : __n(n), body(4 * n + 5), leaves(n + 5) {
rep (j, 1, n) for (int i = 0; i < 4; ++i) leaves[j][i].emplace(INF);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr);
rd(Q);
bsi dat;
rep (i, 1, Q) {
rd(opt[i], cat[i], a[i], b[i]);
dat.pb(cat[i] == 0 ? a[i] - b[i] : b[i] - a[i]);
}
sort(allu(dat)), dat.resize(distance(dat.begin(), unique(allu(dat))));
auto getter = [&](int x) -> int {
return distance(dat.begin(), lower_bound(allu(dat), x)) + 1;
};
const int dataLength = dat.size();
SegmentTree treeask(dataLength);
rep (i, 1, Q) {
int pos = getter(cat[i] == 0 ? a[i] - b[i] : b[i] - a[i]);
assert(1 <= pos && pos <= dataLength);
auto& cur = treeask.leaves[pos];
int idx = 2 * cat[i];
if (opt[i] == 1) cur[idx].emplace(a[i]), cur[idx + 1].emplace(b[i]);
else cur[idx].erase(cur[idx].find(a[i])), cur[idx + 1].erase(cur[idx + 1].find(b[i]));
treeask.upd(pos);
int res = treeask.Ask();
if (res >= INF) cout << "-1\n";
else cout << res << "\n";
}
}