【[NOI2016]区间】

发现自己的离散化姿势一直有问题

今天终于掌握了正确的姿势

虽然这并不能阻挡我noip退役爆零的历史进程

还是先来看看离散化怎么写吧，我以前都是这么写的

for(std::set<int>::iterator it=s.begin();it!=s.end();it++)

	ma[*it]=++tot;

这是使用\(set+map\)的离散化，但是显然巨大的常数是极大的劣势

正确的操作应该是这个样子

std::sort(a+1,a+n+1)

int tot=unique(a+1,a+n+1)-a-1;

for(re int i=1;i<=tot;i++)

	ma[a[i]]=i;

\(unique\)能将一个有序数组去重，返回值是去重之后的尾地址，减去首地址就可以得到去重之后的数量了

之后再来看这道题，也是一道非常神的题

这道题告诉我们暴力通向错误的解，错误的解往往跟正解很接近了

首先\(O(n^2logn)\)还是比较好想的做法，我们先将所有的区间按照长度排序，之后我们定住一个区间作为长度最小的区间，强行套用线段树暴力覆盖之后的比它大的区间，直到这个区间有一个点被覆盖了\(m\)次，那么最后覆盖上去的区间的长度减去定住的最小值就是答案了

对所有的答案取一个\(min\)就好了

这样是显然不行的呀，我们得想个办法

于是我就想出来一种显然错误的做法

我大胆的猜测答案是单调的

少年谁给你的勇气

于是这个显然错误的做法是这样的，先将最短的区间一直覆盖，直到覆盖到符合条件为止，之后由于所谓的"答案单调"，那么使下一个次短的区间符合条件的区间一定在前面的答案的后面

这样的复杂度均摊下来是对的

答案单调很有道理，但是凉凉了

很容易就能找到反例了

我们再覆盖第一个最短的区间的时候，由于我们只是在判断最短的区间是否满足条件，所以可能这个时候之后的某个区间就突然满足条件了，所以这个答案显然不是单调的

但是这个错误的思路和正解已经非常接近了，差别只有一点，我们判断的时候判断的不是最短的区间是否符合条件，而是判断整个区间内是否有点被覆盖了\(m\)次

这有什么道理呢，其实联想一下尺取法，和尺取法差不多

我们从最短的区间开始覆盖，可能覆盖的过程中满足条件的点并没有来自当前的区间，但是没有关系，我们直接用当前的区间作为最小的区间就行了，这样显然只会导致答案偏大，而真正的最小区间我们在后面也会取到

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstring>

#include<set>

#include<algorithm>

#include<map>

#define maxn 500005

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

std::set<int> s;

std::map<int,int> ma;

struct node

{

	int ll,rr,len;

	int L,R;

}a[maxn];

int b[maxn<<1];

int n,m,N;

int ans=19999999999;

int l[4000005],r[4000005],d[4000005],tag[4000005];

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

	  x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

inline int cmp(node K,node M)

{

	return K.len<M.len;

}

void build(int x,int y,int i)

{

	l[i]=x;

	r[i]=y;

	if(x==y) return;

	int mid=x+y>>1;

	build(x,mid,i<<1),build(mid+1,y,i<<1|1);

}

inline void pushdown(int i)

{

	if(!tag[i]) return;

	tag[i<<1]+=tag[i];

	tag[i<<1|1]+=tag[i];

	d[i<<1|1]+=tag[i];

	d[i<<1]+=tag[i];

	tag[i]=0;

}

void change(int x,int y,int v,int i)

{

	if(x<=l[i]&&y>=r[i])

	{

		d[i]+=v;

		tag[i]+=v;

		return;

	}

	pushdown(i);

	int mid=l[i]+r[i]>>1;

	if(y<=mid) change(x,y,v,i<<1);

	else if(x>mid) change(x,y,v,i<<1|1);

	else change(x,y,v,i<<1),change(x,y,v,i<<1|1);

	d[i]=max(d[i<<1],d[i<<1|1]);

}

int main()

{

	n=read();

	m=read();

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

		a[i].ll=read(),a[i].rr=read(),a[i].len=a[i].rr-a[i].ll,b[++N]=a[i].ll,b[++N]=a[i].rr;

	std::sort(a+1,a+n+1,cmp);

	std::sort(b+1,b+N+1);

	int tot=std::unique(b+1,b+N+1)-b-1;

	for(re int i=1;i<=tot;i++)

		ma[b[i]]=i;

	build(1,tot,1);

	for(re int i=1;i<=n;i++) a[i].L=ma[a[i].ll],a[i].R=ma[a[i].rr];

	int now=-1;

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

	{

		change(a[i].L,a[i].R,1,1);

		if(d[1]==m)

		{

			ans=a[i].len-a[1].len;

			now=i;

			break;

		}

	}

	if(now==-1)

	{

		puts("-1");

		return 0;

	}

	for(re int i=2;i<=n;i++)

	{

		change(a[i-1].L,a[i-1].R,-1,1);

		while(d[1]<m)

		{

			if(now==n)

			{

				printf("%d\n",ans);

				return 0;

			}

			now++;

			change(a[now].L,a[now].R,1,1);

		}

		ans=min(ans,a[now].len-a[i].len);

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

【[NOI2016]区间】

最新文章

热门文章