原题网址

https://codeforces.com/contest/1555/problem/E

题目大意

有n个区间。每个区间是[1,m]的子区间。从a可以一步走到b的充要条件是存在区间同时覆盖[a,b]。若n个区间中取出一些区间后，可以只通过被取出的区间从1走到m，则称这些被取出的区间组成的集合A是好的。每个区间有价值w，求一个好的集合A的所有元素中，最大价值与最小价值的差的最小值。

数据结构

线段树，支持以下两种操作：

• 插入或删除区间
• 查询当前区间集合是否为好的

若一个区间集是好的，则1.5，2.5，...，m-0.5都至少被一个区间覆盖，区间[a,b]可以覆盖a+0.5，...，b-0.5。所以我们可以将每个区间的右端点减一后再操作，线段树第a个元素表示a+0.5被多少个区间覆盖。这样只要查询线段树中[1,m-1]最小值是否为0，不为0即好的。

由于m较大，必须使用懒修改方法，每个节点增加lazy值（区别于真正的val值），注意点：

• 访问某节点时，先进行push操作（将本节点lazy值转给val值，如果还有孩子，则lazy值传递给孩子，清空本节点lazy值），不管被查区间是多少（若l>r也要push，因为只要能递归到，就表示该点实际上表示了一个区间，需要把lazy值转给val值）。
• 修改时，如果某个节点表示的区间全都要修改，只修改该节点lazy值，不递归。改完后必须进行push操作，把lazy值转成val并传递给孩子。
• 递归返回时，将两个孩子的val组合成本节点的val。

解题思路

本题为最优化问题。显然尽可能选价值差较小的区间。
先将所有区间按价值排序。
用双指针维护一个已知价值最小值，找到价值最大值最小的好的区间范围。
枚举所有最小值，根据最小值指针和线段树查询结果移动最大值指针并更新最后答案（用最大值-最小值更新ans）。

我的代码

#include <bits/stdc++.h>

using namespace std;

struct seg {
    int l, r, w;
};

bool operator<(const seg& a, const seg& b) { return a.w < b.w; }

vector<seg> seglist;
vector<int> seglazy;
vector<int> segtree;

void push(int v) {
    if (2 * v + 1 < segtree.size()) {
        seglazy[2 * v] += seglazy[v];
        seglazy[2 * v + 1] += seglazy[v];
    }
    segtree[v] += seglazy[v];
    seglazy[v] = 0;
}

void addvalue(int v, int tl, int tr, int l, int r, int val) {
    push(v);
    if (l > r) return;
    if (l == tl && r == tr) {
        seglazy[v] += val;
        push(v);
        return;
    }
    int tm = (tl + tr) / 2;
    addvalue(v * 2, tl, tm, l, min(r, tm), val);
    addvalue(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
    segtree[v] = min(segtree[2 * v], segtree[2 * v + 1]);
}

int get() { return segtree[1] + seglazy[1]; }

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    seglist.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> seglist[i].l >> seglist[i].r >> seglist[i].w;
        --seglist[i].l;
        --seglist[i].r;
    }
    sort(seglist.begin(), seglist.end());
    segtree.resize(m << 2, 0);
    seglazy.resize(m << 2, 0);

    int lp = 0, rp = 0;
    int ans = 1e9;

    for (lp = 0; lp < n; ++lp) {
        while (rp < n && get() == 0) {
            addvalue(1, 0, m - 2, seglist[rp].l, seglist[rp].r - 1, 1);
            ++rp;
        }
        if (get() == 0) break;
        ans = min(ans, seglist[rp - 1].w - seglist[lp].w);
        addvalue(1, 0, m - 2, seglist[lp].l, seglist[lp].r - 1, -1);
    }
    cout << ans << endl;
    return 0;
}

Educational Codeforces Round 112 E、Boring Segments