1 条题解

  • 0
    @ 2026-11-12 21:58:18

    [W] Intervals(dp_w)题解

    题意简述

    构造长度为 NN 的 01 串。给定 MM 个区间 [li,ri][l_i, r_i],若区间内至少有一个 1 则得 aia_i(aia_i 可为负),求最大总分。

    思路

    转化:总分 = 全部 aia_i − 未满足区间的 aia_i

    把所有 aia_i 加起来,得到"假设全部满足"的总分;再从里面减掉那些"一个 1 都没有"的区间带来的 aia_i。于是变成最小化损失。

    0 段的结构

    串中的 1 把串切成若干"全 0 段"。一个区间若全落在某个 0 段内则未被满足;若它跨越了两个不同的 0 段,中间必有 1,则被满足。因此——

    未满足的区间 = 被某个极大 0 段 [i,e][i, e] 完整包含的区间。

    于是只需决定"哪些位置作为 0 段的结束",损失可分解为各 0 段的贡献之和。

    DP 定义

    • GeG_e = 前缀 [1..e][1..e] 且 ee 处为 0 时的最小损失;
    • HeH_e = 前缀 [1..e][1..e] 且 ee 处为 1 时的最小损失。

    转移:

    $$H_e = \min(G_{e-1}, H_{e-1}) \quad (\text{位置 } e \text{ 放 } 1,\text{损失不增加}),$$$$G_e = \min_{i \le e} \left( \text{base}(i) + \text{cost}(i, e) \right),$$

    其中 base(1)=0\text{base}(1) = 0、base(i)=Hi−1\text{base}(i) = H_{i-1}(i≥2i \ge 2),而

    $$\text{cost}(i,e) = \sum_{k:\; i \le l_k,\, r_k \le e} a_k .$$

    用线段树维护 GeG_e

    上式等价于:维护一个数组 vali=base(i)+cost(i,e)\text{val}_i = \text{base}(i) + \text{cost}(i, e),Ge=min⁡i≤evaliG_e = \min_{i \le e} \text{val}_i。

    逐个 ee 推进时:

    1. 激活 ee:把 vale\text{val}_e 从 +∞+\infty 设为 base(e)=He−1\text{base}(e)=H_{e-1}(此前没有合法区间能覆盖"以 ee 结尾的 0 段",所以 ee 处不可能被任何区间贡献,先激活是安全的);
    2. 对每个 rk=er_k = e 的区间,所有满足 i≤lki \le l_k 的 vali\text{val}_i 都要加上 aka_k → 区间加 [1,lk][1, l_k];
    3. Ge=G_e = 区间 [1,e][1, e] 的 最小值。

    最后答案 =∑ai−min⁡(GN,HN)= \sum a_i - \min(G_N, H_N)。

    复杂度

    时间 O((N+M)log⁡N)O((N+M)\log N),空间 O(N)O(N)。

    参考代码

    #include <cstdio>
    #include <climits>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long ll;
    
    vector<ll> mn, lz;
    int n_;
    
    void build(int o, int l, int r) {
        if (l == r) { mn[o] = LLONG_MAX / 4; return; }
        int m = (l + r) >> 1;
        build(o << 1, l, m); build(o << 1 | 1, m + 1, r);
        mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
    }
    void push(int o) {
        if (!lz[o]) return;
        for (int c = o << 1; c <= (o << 1 | 1); c++) { mn[c] += lz[o]; lz[c] += lz[o]; }
        lz[o] = 0;
    }
    void upd(int o, int l, int r, int ql, int qr, ll v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { mn[o] += v; lz[o] += v; return; }
        push(o);
        int m = (l + r) >> 1;
        upd(o << 1, l, m, ql, qr, v); upd(o << 1 | 1, m + 1, r, ql, qr, v);
        mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
    }
    void activate(int o, int l, int r, int pos, ll val) {
        if (l == r) { mn[o] = min(mn[o], val); return; }
        push(o);
        int m = (l + r) >> 1;
        if (pos <= m) activate(o << 1, l, m, pos, val);
        else activate(o << 1 | 1, m + 1, r, pos, val);
        mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
    }
    ll qry(int o, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return LLONG_MAX / 4;
        if (ql <= l && r <= qr) return mn[o];
        push(o);
        int m = (l + r) >> 1;
        return min(qry(o << 1, l, m, ql, qr), qry(o << 1 | 1, m + 1, r, ql, qr));
    }
    
    int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        vector<vector<pair<int, ll>>> byR(n + 1);
        ll total = 0;
        for (int i = 0; i < m; i++) {
            int l, r; ll a;
            scanf("%d %d %lld", &l, &r, &a);
            byR[r].push_back({l, a});
            total += a;
        }
        mn.assign(4 * n + 4, 0); lz.assign(4 * n + 4, 0);
        build(1, 1, n);
        ll H = 0, Gprev = LLONG_MAX / 4, best = 0;
        for (int e = 1; e <= n; e++) {
            activate(1, 1, n, e, (e == 1) ? 0 : H);        // base(e)
            for (auto& pr : byR[e]) upd(1, 1, n, 1, pr.first, pr.second);
            ll G = qry(1, 1, n, 1, e);
            H = (e == 1) ? 0 : min(H, Gprev);
            Gprev = G;
            best = min(G, H);
        }
        printf("%lld\n", total - best);
        return 0;
    }
    

    易错点

    1. 必须先激活叶 ee 再加区间:否则"以 ee 结尾的 0 段"可能被更早的区间错误地累加到 +∞+\infty,导致该段永远不可用。
    2. 激活值应取 He−1H_{e-1}(e=1e=1 取 0),而不是 Ge−1G_{e-1}——位置 e−1e-1 必须是 1 才能把 0 段断开。
    3. 全部 ai>0a_i > 0 时最优是全 1(答案 ∑ai\sum a_i);全负时最优是全 0,但因为要"至少满足"……注意全 0 串也会满足"含 1 至少一次"?不,全 0 时所有区间都不满足,答案 00。
    4. 答案可达 2×10142\times10^{14},必须 long long。

    数据说明

    共 16 组:5 组官方样例;N=1,2,3,5N=1,2,3,5 手工构造;N=10/50/1000N=10/50/1000 随机;N=M=2×105N=M=2\times10^5 全正、全负、混合随机三组,以及"一个大正区间 + 大量小区间"的构造组。

    • 1

    信息

    ID
    32
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    1
    已通过
    1
    上传者