BZOJ 4653: [Noi2016]区间

oi-forever 2018-06-17 原文

4653: [Noi2016]区间

Time Limit: 60 Sec Memory Limit: 256 MB
Submit: 1291 Solved: 683
[Submit][Status][Discuss]

Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],…,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。

Input

第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n

接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。

N<=500000,M<=200000,0≤li≤ri≤10^9

Output

只有一行，包含一个正整数，即最小花费。

Sample Input

6 3
3 5
1 2
3 4
2 2
1 5
1 4

Sample Output

总结：

水题

80分：二分 + 线段树

100分：类似于单调队列的方式，双指针 + 线段树搞

要离散化一下

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

const int maxn = 1000005;
int tag[maxn << 4], val[maxn << 4], n, m;
int p[maxn], tot, ans = 2e9;
struct Node {
	int l, r, val;
	bool operator < (const Node &a) const {
		return val < a.val;
	}
} q[maxn];

int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = x * 10 + ch - 48; ch = getchar();}
	return x * f;
}
void update(int o) {
	val[o] = max(val[o << 1], val[o << 1 | 1]);
}
void pushdown(int o, int l, int r) {
	if(tag[o] != 0) {
		tag[o << 1] += tag[o]; tag[o << 1 | 1] += tag[o];
		val[o << 1] += tag[o]; val[o << 1 | 1] += tag[o];
		tag[o] = 0;
	}
}
void Modify(int o, int l, int r, int ql, int qr, int z) {
	if(ql <= l && r <= qr) {
		tag[o] += z; val[o] += z; return;
	} int mid = (l + r) >> 1; pushdown(o, l, r);
	if(ql <= mid) Modify(o << 1, l, mid, ql, qr, z);
	if(qr > mid) Modify(o << 1 | 1, mid + 1, r, ql, qr, z);
	update(o);
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; ++i) {
		q[i].l = read(); q[i].r = read();
		q[i].val = q[i].r - q[i].l;
		p[++tot] = q[i].l; p[++tot] = q[i].r;
	} sort(q + 1, q + n + 1);
	sort(p + 1, p + tot + 1); tot = unique(p + 1, p + tot + 1) - p - 1;
	for (int i = 1; i <= n; ++i) {
		q[i].l = lower_bound(p + 1, p + tot + 1, q[i].l) - p;
		q[i].r = lower_bound(p + 1, p + tot + 1, q[i].r) - p;
	} int pos = 1;
	for (int i = 1; i <= n; ++i) {
		Modify(1, 1, tot, q[i].l, q[i].r, 1);
		while(val[1] >= m) {
			ans = min(ans, q[i].val - q[pos].val);
			Modify(1, 1, tot, q[pos].l, q[pos].r, -1);
			pos++;
		}
	} (ans == 2e9) ?printf("-1\n") :printf("%d\n", ans);
	return 0;
}