求助，不会做

__er @ 2023-01-15 08:17:22

by 静谧幽蓝 @ 2023-01-15 08:20:39

问一下 m 多少

by __er @ 2023-01-15 08:21:26

@静谧幽蓝 m 不变，在打线段重叠

by __er @ 2023-01-15 08:21:56

by Happy_Orca @ 2023-01-15 08:22:13

@__er 离散，然后二分查找需要移的树木的区间

by ivyjiao @ 2023-01-15 08:22:23

@__er https://www.luogu.com.cn/problem/P1496

by 静谧幽蓝 @ 2023-01-15 08:23:13

那就离散化端点，搞完后最多 2m 个点，然后就暴力做区间覆盖

by 静谧幽蓝 @ 2023-01-15 08:24:37

@__er

by H_Kaguya @ 2023-01-15 08:30:04

也不用离散化，就按左端点排个序，然后从前往后扫一遍就行了，O(mlog m)。

by __er @ 2023-01-15 08:33:23

wssb，打了一个 \mathcal O (m\log m) 的

#include <bits/stdc++.h>
using namespace std;

struct sgm {
    int l, r;
} a[1001];

bool cmp(sgm a, sgm b) {
    return a.l < b.l;
}
int L, m, ans, t;

int main() {
    cin >> L >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + 1 + m, cmp);
    ans = a[1].r - a[1].l + 1, t = a[1].r;
    for (int i = 2; i <= m; i++) {
        if (a[i].l <= t && a[i].r > t) {
            ans += (a[i].r - t), t = a[i].r;
        }
        if (a[i].l > t) {
            ans += a[i].r - a[i].l + 1, t = a[i].r;
        }
    }
    return cout << L + 1 - ans, 0;
}

by dxrS @ 2023-01-15 09:34:55

@__er 珂朵莉数