离散化

俗话说的好，遇到一道题，先看一下数据范围，看看能不能骗分（其实骗分是一种技能），l、r都<=1e9很显然是要离散化了。

离散化模板：

#include <algorithm>
uing namespace std;

for (int i = 1; i <= n; i++)
    b[i] = a[i];

sort(b + 1, b + n + 1); // 先排序
// 因为 unique(b + 1, b + n + 1) 是返回 b + n + 1，所以要 - b - 1
tot = unique(b + 1, b + n + 1) - b - 1; // 再去重

for (int i = 1; i <= n; i++) {
    /*
     *lower_bound(b + 1, b + tot + 1, a[i]) 是在 b 中找到第一个 >= a[i] 的数指针
     *因为 b 中是绝对包含 a[i] 的（b[i] = a[i];）且 b 数组去重了
     *所以lower_bound(b + 1, b + tot + 1, a[i]) 是在 b 中找到值为 a[i] 指针
     *又因为是返回指针，所以要 - b
     */
    a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
}

不会 lower_bound 可以先看最后

错误写法

p[i].l = lower_bound(uni + 1, uni + tot + 1, p[i].l) - (uni + 1);
p[i].r = lower_bound(uni + 1, uni + tot + 1, p[i].r) - (uni + 1);

正确写法

p[i].l = lower_bound(uni + 1, uni + tot + 1, p[i].l) - uni;
p[i].r = lower_bound(uni + 1, uni + tot + 1, p[i].r) - uni;

思路

在看题，“选中的最长区间长度减去被选中的最短区间长度”，题目要求的答案跟“最长”和“最短”有关，所以我们就会联想到单调性。

我们先思考一种较暴力的做法，那就是按排序后的顺序逐一加入区间，然后看看是否有一个点的被覆盖次数>=m。

如果有的话那就取 min{ans, len[i] - len[last]} 其中 len = r - l ，然后将前面加入的按顺序删掉，直到<m。

显然这利用了#&……￥&*%…………@#！（尺取法）的思想。

现在问题就是我们如何快速地得知是否有一个点的被覆盖次数>=m。

那就很显然维护一棵线段树就好了。

细节

线段树模板见 P3372

不知道有没有人query写复杂了，就是tr[1].max鸭，因为每次就是全部最大值

记得判-1鸭（没逝反正测试点会告诉你一切）

然后呢？然后就AC了。

代码

// 区间
// P1712
#include <cstdio>
#include <algorithm>
#define lc u << 1
#define rc u << 1 | 1
#define inf 0x3f3f3f3f

using namespace std;

const int N = 5e5 + 114514; // 预防线段树子结点越界
int n, m, d[N << 1], tot;

struct Node {
    int l, r, len;
}p[N];

struct Tree {
    int l, r;
    int val, tag;
}tre[N << 2]; // 线段树开4倍数组

bool cmp(Node x, Node y) { return x.len < y.len; } // 离散化排序的比较函数

inline void pushup(int u) {
    tre[u].val = max(tre[lc].val, tre[rc].val);
}

void pushdown(int u) {
    if (tre[u].tag) {
        tre[lc].val += tre[u].tag;
        tre[rc].val += tre[u].tag;
        tre[lc].tag += tre[u].tag;
        tre[rc].tag += tre[u].tag;
        tre[u].tag = 0;
    }
}

void build(int u, int l, int r) {
    tre[u] = {l, r, 0, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(u);
}

void change(int u, int l, int r, int v) {
    if (l <= tre[u].l && tre[u].r <= r) {
        tre[u].val += v;
        tre[u].tag += v;
        return;
    }
    int mid = tre[u].l + tre[u].r >> 1;
    pushdown(u);
    if (l <= mid) change(lc, l, r, v);
    if (r > mid) change(rc, l, r, v);
    pushup(u);
}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &p[i].l, &p[i].r);
        p[i].len = p[i].l - p[i].r;
        d[++tot] = p[i].l, d[++tot] = p[i].r; // 离散化数组
    }

    sort(p + 1, p + n + 1, cmp); // 先排序
    sort(d + 1, d + tot + 1); // 再去重
    tot = unique(d + 1, d + tot + 1) - (d + 1);

    for (int i = 1; i <= n; i++) {
        // 二分找到p[i].l 或 p[i].r
        p[i].l = lower_bound(d + 1, d + tot + 1, p[i].l) - d;
        p[i].r = lower_bound(d + 1, d + tot + 1, p[i].r) - d;
    }

    int last = 1, ans = inf;
    build(1, 1, tot);

    // 尺取法求最小花费
    for (int i = 1; i <= n; i++) {
        change(1, p[i].l, p[i].r, 1);
        while (tre[1].val >= m) {
            change(1, p[last].l, p[last].r, -1);
            ans = min(ans, p[i].len - p[last].len);
            last++;
        }
    }

    if (ans == inf) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

完了吗？ NO

lower_bound

首先 lower_bound 在#include <algorithm>中，且要using namespace std; lower_bound 有三个参数

我们举个栗子🌰

int a[9] = {1, 4, 6, 2 ,7, 3, 0, 9, 5, 3}; // 开了一个长度为9的数组
// lower_bound(a, a + 10, 2) 返回 a + 4，lower_bound(a, a + 10, 2) - a 返回 4
cout << lower_bound(a, a + 10, 2) - a << '\n';
// lower_bound(a, a + 10, 2) 返回 a + 8，lower_bound(a, a + 10, 8) - a 返回 8
cout << lower_bound(a, a + 10, 8) - a << '\n';

所以 lower_bound 返回第一个大于等于x的数的指针

再升级一下

int n, a[100]; // 开了一个长度为100的数组
cin >> n;
for (int i = 1; i <= n; i++)
    cin >> a[i];
// 在 a + 1 ~ a + n + 1 中找到第一个大于等于2的数的数的下标
cout << lower_bound(a + 1, a + n + 1, 2) - a << '\n';
// 在 a + 1 ~ a + n + 1 中找到第一个大于等于8的数的数的下标
cout << lower_bound(a + 1, a + n + 1, 8) - a << '\n';

是在看不懂在 WZH 那学 动态开点 虽然更看不懂

推荐给 tiangeyuan2025 $100$ 硬币学习更好的线段树