[NOI2016] 区间

题意

给出 n 个闭区间，要恰好选出 m 个。

如果这 m 个区间存在公共点，那么这个方案合法。方案代价是被选区间中的最长长度减最短长度。

求所有合法方案中的最小代价；如果不存在合法方案，输出 -1。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30;
const int INF = 0x3f3f3f3f;

struct Interval {
    int l, r;
    int len;
};

int n, m;
Interval a[MAXN];
int ans = INF;

void dfs(int idx, int chosen, int cur_l, int cur_r, int min_len, int max_len) {
    if (chosen == m) {
        ans = min(ans, max_len - min_len);
        return;
    }
    if (idx > n) {
        return;
    }
    if (chosen + (n - idx + 1) < m) {
        return;
    }
    if (chosen > 0 && max_len - min_len >= ans) {
        return;
    }

    // 选择当前区间。
    int next_l = a[idx].l;
    int next_r = a[idx].r;
    int next_min_len = a[idx].len;
    int next_max_len = a[idx].len;
    if (chosen > 0) {
        next_l = max(cur_l, a[idx].l);
        next_r = min(cur_r, a[idx].r);
        next_min_len = min(min_len, a[idx].len);
        next_max_len = max(max_len, a[idx].len);
    }

    // 已选区间的公共交集只会越来越小，一旦为空就不可能再变回合法。
    if (next_l <= next_r) {
        dfs(idx + 1, chosen + 1, next_l, next_r, next_min_len, next_max_len);
    }

    // 不选当前区间。
    dfs(idx + 1, chosen, cur_l, cur_r, min_len, max_len);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 这是一个小数据精确暴力：
    // 枚举恰好选哪 m 个区间，再检查它们是否有公共点。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].len = a[i].r - a[i].l;
    }

    dfs(1, 0, -INF, INF, INF, -INF);

    if (ans == INF) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}

brute.cpp 直接枚举选哪 m 个区间，维护这些区间交集的左右边界，再计算最长长度减最短长度。这个思路完全正确，但只能做小数据验证。

真正的关键是不要直接枚举“选哪 m 个”，而要枚举“允许选的长度范围”。

把所有区间按长度从小到大排序。如果某个合法方案中，最短长度是 L，最长长度是 R，那么它选中的所有区间都一定落在长度窗口 [L, R] 内。

反过来，只要某个长度窗口内存在一个点，被至少 m 个区间同时覆盖，那么就可以从这些区间里挑出恰好 m 个，得到一个合法方案。因此答案就等价于：

在长度排序后的区间序列中
找一个最短窗口
使得窗口内某个点的覆盖次数至少是 m

这就可以用双指针来做：

右指针不断加入新区间
左指针在窗口仍然合法时尽量右移

窗口是否合法，需要支持：

加入一个区间
删除一个区间
查询当前是否存在某个点，被至少 m 个区间覆盖

把所有端点离散化后，用线段树维护覆盖次数最大值即可。

加入一个区间 [l, r]，就在离散化后的 [l, r] 上整体加 1；删除时整体减 1。只要线段树根节点维护的最大值 >= m，就说明当前窗口合法。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500000 + 5;
const int MAXP = MAXN << 1;
const int INF = 0x3f3f3f3f;

struct Interval {
    int l, r;
    int len;
};

int n, m;
Interval a[MAXN];
int xs[MAXP];
int xs_cnt;
int seg_max[MAXP << 2];
int lazy_add[MAXP << 2];

bool cmp_len(const Interval &x, const Interval &y) {
    if (x.len != y.len) {
        return x.len < y.len;
    }
    if (x.l != y.l) {
        return x.l < y.l;
    }
    return x.r < y.r;
}

int get_id(int x) {
    return lower_bound(xs + 1, xs + xs_cnt + 1, x) - xs;
}

void push_up(int u) {
    seg_max[u] = max(seg_max[u << 1], seg_max[u << 1 | 1]);
}

void apply_add(int u, int val) {
    seg_max[u] += val;
    lazy_add[u] += val;
}

void push_down(int u) {
    if (lazy_add[u] == 0) {
        return;
    }
    apply_add(u << 1, lazy_add[u]);
    apply_add(u << 1 | 1, lazy_add[u]);
    lazy_add[u] = 0;
}

void range_add(int u, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        apply_add(u, val);
        return;
    }

    push_down(u);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        range_add(u << 1, l, mid, ql, qr, val);
    }
    if (qr > mid) {
        range_add(u << 1 | 1, mid + 1, r, ql, qr, val);
    }
    push_up(u);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].len = a[i].r - a[i].l;
        xs[++xs_cnt] = a[i].l;
        xs[++xs_cnt] = a[i].r;
    }

    sort(xs + 1, xs + xs_cnt + 1);
    xs_cnt = unique(xs + 1, xs + xs_cnt + 1) - (xs + 1);

    for (int i = 1; i <= n; i++) {
        a[i].l = get_id(a[i].l);
        a[i].r = get_id(a[i].r);
    }

    sort(a + 1, a + n + 1, cmp_len);

    int ans = INF;
    int left = 1;
    for (int right = 1; right <= n; right++) {
        // 当前区间加入窗口后，它覆盖的所有坐标点都要 +1。
        range_add(1, 1, xs_cnt, a[right].l, a[right].r, 1);

        // 只要窗口内已经存在某个点被至少 m 个区间覆盖，
        // 就可以尝试收缩左端，更新更小的长度差。
        while (left <= right && seg_max[1] >= m) {
            ans = min(ans, a[right].len - a[left].len);
            range_add(1, 1, xs_cnt, a[left].l, a[left].r, -1);
            left++;
        }
    }

    if (ans == INF) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}

复杂度

排序和离散化都是 $O(n log n)$ 。

双指针过程中，每个区间最多进入窗口一次、离开窗口一次，每次在线段树上的修改是 $O(log n)$ 。

所以总时间复杂度是 $O(n log n)$ ，空间复杂度是 $O(n)$ 。

总结

这题最重要的转化是：

不枚举“选哪 m 个区间”
改为枚举“这些区间的长度落在哪个窗口里”

一旦做完这个转化，整题就变成：

双指针维护最短长度窗口
线段树维护窗口内的最大覆盖次数

这是一个很典型的“排序后枚举答案区间”的思路。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

测试点编号	$ n= $	$ m= $	$ l_i,r_i $
1	$ 20 $	$ 9 $	$ 0 \le l_i \le r_i \le 100 $
2	^	$ 10 $	$ 0 \le l_i \le r_i \le 100 $
3	$ 199 $	$ 3 $	$ 0 \le l_i \le r_i \le 100000 $
4	$ 200 $	^	^
5	$ 1000 $	$ 2 $	^
6	$ 2000 $	^	^
7	$ 199 $	$ 60 $	$ 0 \le l_i \le r_i \le 5000 $
8	$ 200 $	$ 50 $	^
9	^	^	$ 0 \le l_i \le r_i \le 10^9 $
10	$ 1999 $	$ 500 $	$ 0 \le l_i \le r_i \le 5000 $
11	$ 2000 $	$ 400 $	^
12	^	$ 500 $	$ 0 \le l_i \le r_i \le 10^9 $
13	$ 30000 $	$ 2000 $	$ 0 \le l_i \le r_i \le 100000 $
14	$ 40000 $	$ 1000 $	^
15	$ 50000 $	$ 15000 $	^
16	$ 100000 $	$ 20000 $	^
17	$ 200000 $	^	$ 0 \le l_i \le r_i \le 10^9 $
18	$ 300000 $	$ 50000 $	^
19	$ 400000 $	$ 90000 $	^
20	$ 500000 $	$ 200000 $	^

目录

题意

思路

代码

复杂度

总结

一图流解析