【题解】P1712 [NOI2016] 区间

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

在数轴上有\(n\)个闭区间从\(1\)至\(n\)编号，第\(i\)个闭区间为\([l_i,r_i]\)。现在要从中选出\(m\)个区间，使得这\(m\)个区间共同包含至少一个位置。换句话说，就是使得存在一个\(x\)，对于每个被选中的区间\([l_i,r_i]\)，都有\(l_i \le x \le r_i\)。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。

区间 \([l_i,r_i ]\)的长度定义为\((r_i-l_i)\)，即等于它的右端点的值减去左端点的值。求所有合法方案中最小的花费。如果不存在合法的方案，输出\(−1\)。

\(1 \le m \le n,~1 \le n \le 5 \times 10^5,~1 \le m \le 2\times 10^5,~0\le l_i \le r_i \le 10^9\)

分析

根据花费的计算公式：被选中的最长区间长度减去被选中的最短区间长度。

将所有区间按长度排序，让最长区间尽可能小，最短区间尽可能大。 两个指针\(L,R\)表示区间\([L,R]\)间的区间加入。逐一将区间加入，当有一个点的覆盖次数达到\(m\)，统计答案并将前面的区间顺序删掉，直到所有点\(<m\)。重复上面的过程。

如何快速维护区间内点被覆盖的次数？线段树维护区间最值即可。 注意到\(0\le l_i \le r_i \le 10^9\)，我们需要将数据离散化。

实现

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

#define ll long long
#define mid (l+r)/2
#define ls id<<1
#define rs id<<1|1
const ll N = 1000005;
using namespace std;
ll n, m, tmp, uni[N];
struct node {
    ll l, r;
} q[N], bas[N];

bool cmp(node a, node b) {
    return (a.r - a.l) < (b.r - b.l);
}

ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

ll maxn[N << 2], laz[N << 2];

inline void pushup(ll id) {
    maxn[id] = max(maxn[ls], maxn[rs]);
}

void pushdown(ll id) {
    if (!laz[id]) return;
    maxn[ls] += laz[id];
    maxn[rs] += laz[id];
    laz[ls] += laz[id];
    laz[rs] += laz[id];
    laz[id] = 0;
}

void update(ll id, ll l, ll r, ll x, ll y, ll v) {
    //cout<<id<<" "<<x<<" "<<y<<endl;
    if(y<l || x>r) return;
    if (l >= x && r <= y) {
        maxn[id] += v;
        laz[id] += v;
        return;
    }
    pushdown(id);
    if (x <= mid) update(ls, l, mid, x, y, v);
    if (y > mid) update(rs, mid + 1, r, x, y, v);
    pushup(id);
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        q[i].l = bas[i].l = read();
        q[i].r = bas[i].r = read();
        uni[++tmp] = q[i].l;
        uni[++tmp] = q[i].r;
    }
    sort(uni + 1, uni + tmp + 1);
    tmp = unique(uni + 1, uni + tmp + 1) - uni - 1;
    sort(q + 1, q + n + 1, cmp);
    sort(bas + 1, bas + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        q[i].l = lower_bound(uni + 1, uni + tmp + 1, q[i].l) - uni;
        q[i].r = lower_bound(uni + 1, uni + tmp + 1, q[i].r) - uni;
    }

    ll L = 0, R = 0, ans = 1e18;
    while (true) {
        while (maxn[1] < m && R <= n) {
            R++;
            update(1, 1, tmp, q[R].l, q[R].r, 1);
        }
        if (maxn[1] < m) break;
        while (maxn[1] >= m && L <= n) {
            L++;
            update(1, 1, tmp, q[L].l, q[L].r, -1);
        }
        
        ans = min(ans, (bas[R].r - bas[R].l) - (bas[L].r - bas[L].l));
    }
    if (ans == 1e18) puts("-1");
    else printf("%lld\n", ans);
    return 0;
}