Boring Segments

发表于 分类于 ，

    在一个 $[1,m]$ 的数轴上有 n 条线段，第 i 条覆盖了 $[l_i,r_i]$ 的区间，权值为 $w_i$ ，你的任务是从这些线段中选出若干条首尾相接线段覆盖整个数轴，使得这些线段权值极差最小化，输出这个极差

    首尾相接的定义是，假设你有机会从同一条线段覆盖的任意两个点中移动，如果你可以从位置 1 出发，经过一些线段到达位置 m ，就称为这些线段首尾相接

Boring Segments

Created by LXC on Wed Apr 3 17:07:12 2024

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

ranting: 2100

tag: data structures, sortings, trees, two pointers

problem

在一个 $[1,m]$ 的数轴上有 n 条线段，第 i 条覆盖了 $[l_i,r_i]$ 的区间，权值为 $w_i$ ，你的任务是从这些线段中选出若干条首尾相接线段覆盖整个数轴，使得这些线段权值极差最小化，输出这个极差

首尾相接的定义是，假设你有机会从同一条线段覆盖的任意两个点中移动，如果你可以从位置 1 出发，经过一些线段到达位置 m ，就称为这些线段首尾相接

solution

将线段按照权值排序后得到新数组d，d中的一个子数组的所有线段如果能够覆盖1到m，称这个子数组合法。那么包含了这个子数组的子数组也合法，满足区间包含性。我们用滑动窗口来求最小长度的合法子数组。

需要高效判断窗口内线段能否覆盖1到m。用线段树，窗口内增加一个线段[l,r]则在线段树区间[l,r-1]上加1，窗口内减少一个线段[l,r]则在线段树区间[l,r-1]上减1，然后线段树维护区间上的最小值，只要1到m这个区间最小值不是0，则覆盖了整个区间。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1000005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

// 可区间增加，求维护区间最小值
// 可查询区间是否覆盖
#define LS (id << 1)
#define RS (id << 1 | 1)
ll tag[4 * N], mn[4 * N];

void push_up(int id) {
    mn[id] = min(mn[LS], mn[RS]);
}

void push_down(int id) {
    if (tag[id]) {
        mn[LS] += tag[id];
        mn[RS] += tag[id];
        tag[LS] += tag[id];
        tag[RS] += tag[id];
        tag[id] = 0;
    }
}

void build(int id, int l, int r) {
    tag[id] = mn[id] = 0;
    if (l == r) {
        return;
    }
    int m = l + r >> 1;
    build(LS, l, m);
    build(RS, m + 1, r);
    push_up(id);
}

// 区间增加v
void add(int id, int l, int r, int ql, int qr, ll v) {
    if (ql <= l && r <= qr) {
        mn[id] += v;
        tag[id] += v;
        return;
    }
    push_down(id);
    int m = l + r >> 1;
    if (ql <= m)
        add(LS, l, m, ql, qr, v);
    if (m < qr)
        add(RS, m + 1, r, ql, qr, v);
    push_up(id);
}

struct Node {
    int l, r, w;
    Node(int l=0, int r=0, int w=0):l(l),r(r),w(w) {}
    bool operator<(const Node& o) const {
        return w < o.w;
    }
};
ostream& operator<<(ostream& os, const Node& v) {
    os<<'['; 
    auto [l, r, w] = v;
    os << l << ", " << r << ", " << w;
    return os<<']';
}

void sol() {
    int n, m;
    cin >> n >> m;
    vector<Node> a(n);
    for (auto& [l,r,w]:a) cin >> l >> r >> w, r--;
    sort(a.begin(), a.end());
    // cout << a << endl;
    build(1, 1, m-1);
    ll ans = 1e9;
    for (int l=0, r=0; l<n; l++) {
        while (r<n && mn[1] == 0) {
            add(1, 1, m-1, a[r].l, a[r].r, 1);
            r++;
        }
        // cout << l << " " << r << endl;
        // cout << mn[1] << "\n";
        if (mn[1] != 0)
            ans = min(ans, (a[r-1].w - a[l].w)*1LL);
        add(1, 1, m-1, a[l].l, a[l].r, -1);
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}