洛谷 P1712 [NOI2016] 区间

很多套路糅合在一起的一道题。

记 \(len_i = r_i - l_i\)。

则所求转化为一个有 \(m\) 个区间的集合 \(S\)，满足：

• 存在一个 \(x\)，使得对于所有 \(S\) 中的区间 \(i\)，有 \(l_i \le x \le r_i\)。
• \(\max\limits_{i \in S}\{len_i\} - \min\limits_{i \in S}\{len_i\}\) 最小。

对于第二个限制条件，套路地想到按区间长度排序后尺取。

此时时间复杂度为 \(\mathcal{O}(n)\)，也就是说，要在 \(\mathcal{O}(\log n)\) 的时间复杂度内进行第一个限制条件的判断。

对于第一个限制条件，\(l_i, r_i \le 10^9\)，但 \(n \le 5 \times 10^5\)，离散化后即可实现 \(l_i, r_i \le 10^6\)。开一个线段树，维护被覆盖次数最多的点被覆盖的次数，每次只需判断 \(1\) 号结点上的值是否 \(\ge m\) 即可。

时间复杂度 \(\mathcal{O}(n \log n)\)。

代码：

#include <bits/stdc++.h>

#define MAXN 500100
#define lson pos << 1
#define rson pos << 1 | 1

using namespace std;

int n, m, tmp[MAXN << 1];

struct Seg {
    int w, lazy;
} t[MAXN << 3];

struct Node {
    int l, r;

    bool operator<(const Node &rhs) const {
        return r - l > rhs.r - rhs.l;
    }
} a[MAXN], b[MAXN];

template<typename _T>
void read(_T &_x) {
    _x = 0;
    _T _f = 1;
    char _ch = getchar();
    while (_ch < '0' || '9' < _ch) {
        if (_ch == '-') _f = -1;
        _ch = getchar();
    }
    while ('0' <= _ch && _ch <= '9') {
        _x = (_x << 3) + (_x << 1) + (_ch & 15);
        _ch = getchar();
    }
    _x *= _f;
}

template<typename _T>
void write(_T _x) {
    if (_x < 0) {
        putchar('-');
        _x = -_x;
    }
    if (_x > 9) write(_x / 10);
    putchar('0' + _x % 10);
}

void pushdown(int pos) {
    if (!t[pos].lazy) return;
    t[lson].w += t[pos].lazy, t[rson].w += t[pos].lazy;
    t[lson].lazy += t[pos].lazy, t[rson].lazy += t[pos].lazy;
    t[pos].lazy = 0;
}

void upd(int pos, int l, int r, int x, int y, int c) {
    if (x <= l && r <= y) {
        t[pos].w += c;
        t[pos].lazy += c;
        return;
    }
    pushdown(pos);
    int mid = (l + r) >> 1;
    if (x <= mid) upd(lson, l, mid, x, y, c);
    if (y > mid) upd(rson, mid + 1, r, x, y, c);
    t[pos].w = max(t[lson].w, t[rson].w);
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) {
        read(a[i].l), read(a[i].r);
        tmp[++tmp[0]] = a[i].l, tmp[++tmp[0]] = a[i].r;
    }
    sort(a + 1, a + n + 1);
    sort(tmp + 1, tmp + tmp[0] + 1);
    for (int i = 1; i <= n; i++) {
        b[i].l = lower_bound(tmp + 1, tmp + tmp[0] + 1, a[i].l) - tmp;
        b[i].r = lower_bound(tmp + 1, tmp + tmp[0] + 1, a[i].r) - tmp;
    }
    int l = 1, r = 0, ans = 2e9;
    while (r < n) {
        while (t[1].w < m && r < n) {
            r++;
            upd(1, 1, tmp[0], b[r].l, b[r].r, 1);
        }
        while (t[1].w >= m && l <= r) {
            ans = min(ans, (a[l].r - a[l].l) - (a[r].r - a[r].l));
            upd(1, 1, tmp[0], b[l].l, b[l].r, -1);
            l++;
        }
    }
    write(ans == 2e9 ? -1 : ans);
    return 0;
}