建议投稿到休闲娱乐

Register_int · 2026-10-21 13:45:29 · 题解

大家好啊，看着题解区千篇一律的简洁做法是不是感觉有点枯燥了？我来提供一个锤子做法给大家乐一乐。

静态的问题显然就是反悔贪心。我们从右往左贪，能拿就拿，如果拿了会让左括号太多，就把之前最小的那个左括号扔掉。

现在这个东西要带修，看上去形式并不是很好，所以先对要维护的元素做一个简化。不妨枚举一个 k，将所有数分为 <k 和 \ge k 两种。根据反悔贪心的过程，我们知道：我们一定会选尽可能多的 \ge k 的数。将前者设为 -1，后者设为 1，找到序列的最大后缀和 s，那么我们在开头应该要扔掉 \lceil s/2\rceil 个数不选。对值域离散化后，将所有答案乘上对应的值域段长度并求和，即可得到原问题的答案。

于是转化为这个问题：维护 V 个 1,-1 序列，支持以下操作：

给定 x 并选择头尾一段，将前 x 个序列推入一个 -1，后 V-x 个推入一个 1。
设第 i 个序列对应的值域段长度为 w_i，所有后缀和的最大值为 x_i，求 \sum_i w_i\lceil x/2\rceil。

维护每个序列的最大后缀和 x_i 与总和 s_i，在值域上开线段树。则尾端插入相当于两个对 x_i 区间加和一次 x_i 全局对 0 取 \max，头端插入相当于两个对 s_i 区间加和全局 x_i 对 s_i 取 \max。由于 x_i,s_i 都是单调的，其实只有一段前缀或后缀需要进行修改操作，可以上线段树打标记。统计 \lceil x/2\rceil 也好解决，可以拆成 (x+(x\bmod 2))/2，分别维护两个的和即可。

总时间复杂度同样为 \mathcal{O}(q\log q)！但是常数多大代码要多写多少你别问，嘻嘻。

:::info[Code]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 4e5 + 10;
const int MAXM = 8e5 + 10;

int b[MAXM], m;

struct node {
    ll x, s; int ox, os;
    int lx, rx, ls, rs;
    int tp, tx, ts;
} t[MAXM << 2];

void build(int l = 1, int r = m, int p = 1) {
    auto &_ = t[p]; _.x = _.s = _.ox = _.os = 0;
    _.lx = _.rx = _.ls = _.rs = _.tp = _.tx = _.ts = 0;
    if (l == r) return ; int mid = l + r >> 1;
    build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

inline 
void pushup(int p) {
    auto &_ = t[p], &l = t[p << 1], &r = t[p << 1 | 1];
    _.x = l.x + r.x, _.s = l.s + r.s;
    _.ox = l.ox + r.ox, _.os = l.os + r.os;
    _.lx = l.lx, _.rx = r.rx, _.ls = l.ls, _.rs = r.rs;
}

inline 
void upd(int p, int l, int r, int dx, int ds) {
    auto &_ = t[p]; int w = b[r] - b[l - 1];
    _.x += (ll)dx * w, _.s += (ll)ds * w;
    _.lx += dx, _.rx += dx, _.ls += ds, _.rs += ds;
    if (dx & 1) _.ox = w - _.ox; if (ds & 1) _.os = w - _.os;
    _.tp == 2 ? _.tx += dx - ds : _.tx += dx, _.ts += ds;
}

inline 
void setval(int p, int l, int r, int x) {
    auto &_ = t[p]; int w = b[r] - b[l - 1];
    _.x = (ll)w * x, _.ox = x & 1 ? w : 0, _.lx = _.rx = x;
    _.tp = 1, _.tx = x;
}

inline 
void align(int p, int l, int r, int c) {
    auto &_ = t[p]; int w = b[r] - b[l - 1];
    _.x = _.s + (ll)c * w, _.ox = c & 1 ? w - _.os : _.os;
    _.lx = _.ls + c, _.rx = _.rs + c;
    _.tp = 2, _.tx = c;
}

inline 
void pushdown(int p, int l, int r) {
    auto &_ = t[p]; int mid = l + r >> 1;
    if (!_.tp) {
        upd(p << 1, l, mid, _.tx, _.ts);
        upd(p << 1 | 1, mid + 1, r, _.tx, _.ts);
    } else {
        upd(p << 1, l, mid, 0, _.ts);
        upd(p << 1 | 1, mid + 1, r, 0, _.ts);
        if (_.tp == 1) {
            setval(p << 1, l, mid, _.tx);
            setval(p << 1 | 1, mid + 1, r, _.tx);
        } else {
            align(p << 1, l, mid, _.tx);
            align(p << 1 | 1, mid + 1, r, _.tx);
        }
    }
    _.tp = _.tx = _.ts = 0;
}

void add(int k, bool fl, int l = 1, int r = m, int p = 1) {
    if (r <= k || l > k) {
        int w = r <= k ? 1 : -1;
        return upd(p, l, r, fl ? 0 : w, w);
    }
    int mid = l + r >> 1; pushdown(p, l, r);
    add(k, fl, l, mid, p << 1), add(k, fl, mid + 1, r, p << 1 | 1), pushup(p);
}

void modify_l(int l = 1, int r = m, int p = 1) {
    if (t[p].lx >= t[p].ls) return ;
    if (t[p].rx <= t[p].rs) return align(p, l, r, 0);
    int mid = l + r >> 1; pushdown(p, l, r);
    modify_l(l, mid, p << 1), modify_l(mid + 1, r, p << 1 | 1), pushup(p);
}

void modify_r(int l = 1, int r = m, int p = 1) {
    if (t[p].rx >= 0) return ;
    if (t[p].lx < 0) return setval(p, l, r, 0);
    int mid = l + r >> 1; pushdown(p, l, r);
    modify_r(l, mid, p << 1), modify_r(mid + 1, r, p << 1 | 1), pushup(p);
}

inline 
void insert(int k, int fl) {
    k = lower_bound(b + 1, b + m + 1, k) - b; 
    add(k, fl), fl ? modify_l() : modify_r();
}

int T, n, op[MAXN], x[MAXN], y[MAXN];

int main() {
    freopen("brackets.in", "r", stdin);
    freopen("brackets.out", "w", stdout);
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &n), m = 0;
        for (int i = 1; i <= n; i++) scanf("%d%d%d", &op[i], &x[i], &y[i]);
        for (int i = 1; i <= n; i++) b[++m] = x[i], b[++m] = y[i];
        sort(b + 1, b + m + 1), m = unique(b + 1, b + m + 1) - b - 1;
        b[0] = b[1], build(); ll sum = 0;
        for (int i = 1; i <= n; i++) {
            if (op[i] == 1) insert(x[i], 1), insert(y[i], 1);
            else if (op[i] == 2) insert(x[i], 1), insert(y[i], 0);
            else insert(x[i], 0), insert(y[i], 0); sum += x[i] + y[i];
            printf("%lld\n", sum - (ll)b[1] * i - (t[1].x + t[1].ox >> 1));
        }
    }
}

:::