Solution -「模拟赛」草莓蛋糕

  \(\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";
    }
}