題解 DTOJ #2802. 區間（interval）

歡迎通路 My Luogu Space。

【題目大意】

在數軸上有 n n n 個區間，請選出最少 m m m 個區間，使得這 m m m 個區間至少共同包含一個位置。

選取的花費是選出的區間中最長的區間的長度減去最短的區間的長度。請求出最小花費。如果無法選出則輸出“-1”。

【題解】

線段樹

由于我們的花費是最長和最短的區間的長度的內插補點，具有單調性，是以我們可以将區間的長度排序，用線段樹維護被最多區間覆寫的點的覆寫數。

我們将區間從小到大放入線段樹，直到線段樹根節點的值等于 m m m，說明有某一個點被 m m m 個區間覆寫了，此時統計答案，然後将最早加入的區間删去，再統計答案然後删去，繼續直到線段樹根的值小于 m m m。由于取到了大于 m m m 個區間沒有意義，這樣統計出來的答案就會最優。

最後，區間位置需要離散化。離散化用unique，不要用map，不然會很慢。

【代碼】

// output format !!!
// long long !!!
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN = 500000+10;
struct DATA{
	int l, r, len;
	bool operator<(DATA a)const{
		return len < a.len;
	}
}s[MAXN];

int n, m, ct;
int t[MAXN*8], laz[MAXN*8];
vector<int> C;

#define ls (x<<1)
#define rs (x<<1|1)
void spread(int x, int l, int r){
	int mid = (l+r)>>1;
	t[ls] += laz[x];
	t[rs] += laz[x];
	laz[ls] += laz[x];
	laz[rs] += laz[x];
	laz[x] = 0;
}
void modify(int x, int l, int r, int ql, int qr, int v){
	if(ql<=l && r<=qr){
		t[x] += v;
		laz[x] += v;
		return;
	}
	if(laz[x]) spread(x, l, r);
	int mid = (l+r)>>1;
	if(ql <= mid) modify(ls, l, mid, ql, qr, v);
	if(qr > mid) modify(rs, mid+1, r, ql, qr, v);
	t[x] = max(t[ls], t[rs]);
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i){
		scanf("%d%d", &s[i].l, &s[i].r);
		s[i].len = s[i].r-s[i].l;
		C.push_back(s[i].l);
		C.push_back(s[i].r);
	}
	sort(C.begin(), C.end());
	for(int i=1; i<=n; ++i){
		s[i].l = lower_bound(C.begin(), C.end(), s[i].l)-C.begin()+1;
		s[i].r = lower_bound(C.begin(), C.end(), s[i].r)-C.begin()+1;
	}
	sort(s+1, s+n+1);
	int L=1, R=0, ans=1e9;
	while(R < n){
		while(t[1]<m && R<n) ++R, modify(1, 1, n+n, s[R].l, s[R].r, 1);
		if(t[1]<m && R==n) break;
		while(t[1]>=m && L<=n){
			ans = min(ans, s[R].len-s[L].len);
			modify(1, 1, n+n, s[L].l, s[L].r, -1);
			++L;
		}
	}
	printf("%d", ans==1e9?-1:ans);
	return 0;
}