[NOI2016]区间

LG传送门

考虑到这题的代价是最长边减最短边，可以先把边按长度排个序，双指针维护一个尺取的过程，如果存在包含某个点的区间数\(\ge m\)，就更新答案并把左指针右移，这样做的正确性显然。考虑怎样维护是否有覆盖数\(\ge m\)的点，将线段的端点离散化之后用一棵权值线段树直接维护就行了。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define R register

#define I inline

#define B 1000000

using namespace std;

const int N = 500003, S = 1e9;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1==p2) ? EOF : *p1++; }

I int rd() {

    R int f = 0;

    R char c = gc();

    while (c < 48 || c > 57) c = gc();

    while (c > 47 && c < 58) f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int a[N << 1];

struct segment { int l, r, d; }s[N];

struct segtree { int v, d; }e[N << 3];

I int operator < (segment x, segment y) { return x.d < y.d; }

I int min(int x, int y) { return x < y ? x : y; }

I int max(int x, int y) { return x > y ? x : y; }

I void update(int k, int v) { e[k].v += v, e[k].d += v; }

I void pushup(int k, int p, int q) { e[k].v = max(e[p].v, e[q].v); }

I void pushdown(int k, int p, int q) {

    if (e[k].d)

        update(p, e[k].d), update(q, e[k].d), e[k].d = 0;

}

void modify(int k, int l, int r, int x, int y, int v) {

    if (x <= l && r <= y) {

        update(k, v);

        return ;

    }

    R int p = k << 1, q = p | 1, m = l + r >> 1;

    pushdown(k, p, q);

    if (x <= m)

        modify(p, l, m, x, y, v);

    if (m < y)

        modify(q, m + 1, r, x, y, v);

    pushup(k, p, q);

}

int main() {

    R int n = rd(), m = rd(), i, j, k, x, y, ans = S;

    for (i = 1; i <= n; ++i)

        a[i] = x = rd(), a[i + n] = y = rd(), s[i] = (segment){x, y, y - x};

    sort(s + 1, s + n + 1), sort(a + 1, a + (n << 1 | 1)), k = unique(a + 1, a + (n << 1 | 1)) - a - 1;

    for (i = 1, j = 1; i <= n; ++i) {

        modify(1, 1, k, lower_bound(a + 1, a + k + 1, s[i].l) - a, lower_bound(a + 1, a + k + 1, s[i].r) - a, 1);

        while (e[1].v > m)

            modify(1, 1, k, lower_bound(a + 1, a + k + 1, s[j].l) - a, lower_bound(a + 1, a + k + 1, s[j].r) - a, -1), ++j;

        while (e[1].v == m)

            ans = min(ans, s[i].d - s[j].d), modify(1, 1, k, lower_bound(a + 1, a + k + 1, s[j].l) - a, lower_bound(a + 1, a + k + 1, s[j].r) - a, -1), ++j;

    }

    ans ^ S ? printf("%d", ans) : printf("-1");

    return 0;

}