区间选点最小极差(Intervals) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Seg {
    int l, r, len;
    bool operator<(const Seg& o) const {
        return len < o.len;
    }
};

vector<int> mxT, tagT;

void apply(int u, int v) {
    mxT[u] += v;
    tagT[u] += v;
}

void push(int u) {
    if (tagT[u] != 0) {
        apply(u << 1, tagT[u]);
        apply(u << 1 | 1, tagT[u]);
        tagT[u] = 0;
    }
}

void update(int u, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        apply(u, v);
        return;
    }
    push(u);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(u << 1, l, mid, ql, qr, v);
    if (qr > mid) update(u << 1 | 1, mid + 1, r, ql, qr, v);
    mxT[u] = max(mxT[u << 1], mxT[u << 1 | 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Seg> segs(n);
    vector<int> coords;
    coords.reserve(2 * n);
    for (int i = 0; i < n; ++i) {
        cin >> segs[i].l >> segs[i].r;
        segs[i].len = segs[i].r - segs[i].l;
        coords.push_back(segs[i].l);
        coords.push_back(segs[i].r);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    int K = (int)coords.size();
    for (int i = 0; i < n; ++i) {
        segs[i].l = (int)(lower_bound(coords.begin(), coords.end(), segs[i].l) - coords.begin()) + 1;
        segs[i].r = (int)(lower_bound(coords.begin(), coords.end(), segs[i].r) - coords.begin()) + 1;
    }
    sort(segs.begin(), segs.end());
    mxT.assign(4 * K + 5, 0);
    tagT.assign(4 * K + 5, 0);
    const int INF = 2000000005;
    int ans = INF;
    int L = 0;
    for (int R = 0; R < n; ++R) {
        update(1, 1, K, segs[R].l, segs[R].r, 1);
        while (mxT[1] >= m) {
            ans = min(ans, segs[R].len - segs[L].len);
            update(1, 1, K, segs[L].l, segs[L].r, -1);
            ++L;
        }
    }
    cout << (ans == INF ? -1 : ans) << "\n";
    return 0;
}