夏晓光(loveJY)的博客

NOI2016D1T1

其实相当简单,我一开始想了一个在序列上暴力用平衡树维护差分的做法,就是开三个平衡树?,其中中间一个保持大小为M,就是维护答案集合,其他两个一个维护比答案集合中最大值大的值,一个比最小值小的值,那么打好差分标记后加入删除对应也很简单,但是很容易T掉

我们看到最大值-最小值最大这个显然就是尺取,尺取这个最大值-最小值,那么显然是在值域上尺取,所以我们要按照每条线段的长度排序尺取

有了这个想法,如何满足恰好M的限制呢?线段树区间加线段,如果全局最大值>=m说明此时合法了,不难看出尺取法的删线段在线段树上也很好维护,这样就可以做到$O(nlogn)$了

code:
虽然丑但是是本人写的

//From:Dawn light
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=6e5+7;
vector<int> v;
int n,m;
struct node {
	int mx,ad;
} tr[MAXN<<2];

struct rec {
	int l,r,len;
	bool operator<(const rec &x)const {
		return len<x.len;
	}
} a[MAXN];

#define mid ((x+y)>>1)
#define ls (k<<1)
#define rs (k<<1|1)

inline void pushup(int k) {
	tr[k].mx=max(tr[ls].mx,tr[rs].mx);
}

inline void pushdown(int k) {
	if(tr[k].ad) {
		tr[ls].ad+=tr[k].ad;
		tr[ls].mx+=tr[k].ad;
		tr[rs].ad+=tr[k].ad;
		tr[rs].mx+=tr[k].ad;
		tr[k].ad=0;
	}
}

inline void add(int k,int x,int y,int l,int r,int va) {
//	printf("%d %d %d %d %d\n",k,x,y,l,r);
	if(x>=l&&y<=r) {
		tr[k].ad+=va;
		tr[k].mx+=va;
		return ;
	}

	pushdown(k);
	if(l<=mid)add(ls,x,mid,l,r,va);
	if(r>mid)add(rs,mid+1,y,l,r,va);
	pushup(k);
}

int main() {
	//freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) {
		scanf("%d%d",&a[i].l,&a[i].r);
		v.push_back(a[i].l);
		v.push_back(a[i].r);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1; i<=n; ++i) {
		a[i].len=a[i].r-a[i].l;
		a[i].l=lower_bound(v.begin(),v.end(),a[i].l)-v.begin();
		a[i].r=lower_bound(v.begin(),v.end(),a[i].r)-v.begin();
		//	printf("%d %d\n",a[i].l,v[a[i].l]);
	}
	sort(a+1,a+n+1);
//	for(int i=1; i<=n; ++i) {
//		printf("%d %d\n",v[a[i].l],v[a[i].r]);
//	}
	int L=1,R=0;
	ll ans=1e18;
	for(R=1; R<=n; ++R) {

		add(1,1,2*n+2,a[R].l+1,a[R].r+1,1);
		//	if(tr[1].mx>=m)ans=min(ans,1ll*v[a[R].r]-v[a[R].l]-v[a[L].r]+v[a[L].l]);

		while(tr[1].mx==m) {
			ans=min(ans,1ll*a[R].len-a[L].len);
			//	puts("qwq");
			//	printf("%d %d %d\n",L,R,ans);
			add(1,1,2*n+2,a[L].l+1,a[L].r+1,-1);
			++L;
		}
	}
	if(ans>1e17)return puts("-1"),0;
	printf("%d\n",ans);
	return 0;

}