[NOI2016]区间
考虑到这题的代价是最长边减最短边,可以先把边按长度排个序,双指针维护一个尺取的过程,如果存在包含某个点的区间数\(\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;
}