题目地址：洛谷：【P1712】[NOI2016]区间 – 洛谷、BZOJ：Problem 4653. — [Noi2016]区间

题目描述

在数轴上有 n个闭区间 [l1,r1],[l2,r2],…,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。

题意简述

给你$n$个区间，求选取这些区间的一个子集，使得这个子集中的区间交集不为空，一种选区方案的花费定义为最长区间长度减去最短区间长度，求花费最小的选取方案。

输入输出格式

输入格式：
第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n
接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。
N<=500000,M<=200000,0≤li≤ri≤10^9

输出格式：
只有一行，包含一个正整数，即最小花费。

输入输出样例

输入样例#1：

6 3
3 5
1 2
3 4
2 2
1 5
1 4

输出样例#1：

2

题解

我们对区间按长度排序，贪心地选择尽量短的长度单调的一段，使得这一段中存在一个点被覆盖了至少$m$次，则我们可以用这一段的最长长度减最短长度更新答案。可以证明，这样做一定能找到最优解，相当于在枚举每一个最短长度，贪心地找到最小的最长长度。
判断是否被覆盖$m$次，只需要把区间覆盖转换成线段树上的区间加法，维护全局最大即可。
复杂度$O(n \log n)$。由于左右端点比较大需要离散化。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    register char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 500005;

int n, m, N;

struct Seg {
    int l, r, len;
    inline bool operator<(const Seg &rhs) const {
        return len < rhs.len;
    }
} segs[MAXN];

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

int mx[MAXN << 3], tag[MAXN << 3];

inline void pushdown(int o) {
    if(tag[o]) {
        tag[lch] += tag[o]; tag[rch] += tag[o];
        mx[lch] += tag[o]; mx[rch] += tag[o];
        tag[o] = 0;
    }
}

void add(int o, int l, int r, int ll, int rr, int v) {
    if(l >= ll && r <= rr) {
        mx[o] += v; tag[o] += v; return;
    }
    pushdown(o);
    if(ll <= mid) add(lch, l, mid, ll, rr, v);
    if(rr > mid) add(rch, mid + 1, r, ll, rr, v);
    mx[o] = std::max(mx[lch], mx[rch]);
}

std::vector<int> tmp;

int main() {
    n = readint(); m = readint();
    tmp.push_back(-1);
    for(int i = 1; i <= n; i++) {
        segs[i].l = readint(); segs[i].r = readint();
        segs[i].len = segs[i].r - segs[i].l;
        tmp.push_back(segs[i].l);
        tmp.push_back(segs[i].r);
    }
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    N = tmp.size() - 1;
    for(int i = 1; i <= n; i++) {
        segs[i].l = std::lower_bound(tmp.begin(), tmp.end(), segs[i].l) - tmp.begin();
        segs[i].r = std::lower_bound(tmp.begin(), tmp.end(), segs[i].r) - tmp.begin();
    }
    std::sort(segs + 1, segs + n + 1);
    int r = 0, ans = 2e9;
    for(int l = 1; l <= n; l++) {
        while(r < n && mx[1] < m) {
            r++; add(1, 1, N, segs[r].l, segs[r].r, 1);
        }
        if(mx[1] >= m) ans = std::min(ans, segs[r].len - segs[l].len);
        add(1, 1, N, segs[l].l, segs[l].r, -1);
    }
    printf("%d", ans == 2e9 ? -1 : ans);
    return 0;
}