[数据结构与算法]CF1555E Boring Segments题解--zhengjun

题目大意

给你 $n$ 个区间 $[l_i,r_i]$ 以及每个区间的权值 $w_i$，要求选择一些区间出来覆盖区间 $[1,m]$ （要求区间首尾相接），求选择的区间的 $w$ 的极差的最小值。

思路

看到极差的最小值，想到二分，但不会验证，放弃！

然后分析了一下，这个首尾相接就很难受，我们可以把所有区间的右端点都减一（包括区间 $[1,m]$ ），就不需要首尾相接了，只要把每个点都覆盖到就好了。

接着我们考虑，最后选出来的区间的 $w$ 如果在 $[a,b]$ 之间的话，那么验证的话只要看看所有 $w$ 在 $[a,b]$ 之间的区间能否覆盖所有点就好了。

但是这样枚举 $[a,b]$ 这个区间的复杂度很高。

我们考虑优化这个过程。

首先，枚举一个 $a$ 是逃不掉的，那么，可以发现，当 $a$ 增长的时候， $b$ 也在增长，所以可以从小到大枚举 $a$ ，然后 two-pointers 将 $b$ 向右移，然后验证是否能完全覆盖就好了。

验证能否覆盖所有点的话，那就维护一个线段树，维护区间中被覆盖到的区间数 || 最小的点 || 的被覆盖到的区间数（这句话有点难理解，但真的很重要，停顿都标好了(* ^ ▽ ^ *)），然后就直接线段树上区间加，查询区间 $[1,m?1]$ 的最小值就好了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
void read(){}
template<typename _Tp,typename... _Tps>
void read(_Tp &x,_Tps &...Ar){
	x=0;char c=getchar();bool flag=0;
	while(c<'0'||c>'9')flag|=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	if(flag)x=-x;
	read(Ar...);
}
const int N=3e5+10,M=1e6+10;
int n,m;
struct zj{
	int l,r,w;
	bool operator < (const zj &x)const{
		return w<x.w;
	}
}a[N];
int minx[M<<2],f[M<<2];
void pushup(int rt){
	minx[rt]=min(minx[rt<<1],minx[rt<<1|1]);
}
void pushdown(int rt){
	if(f[rt]){
		minx[rt<<1]+=f[rt];
		minx[rt<<1|1]+=f[rt];
		f[rt<<1]+=f[rt];
		f[rt<<1|1]+=f[rt];
		f[rt]=0;
	}
}
void update(int l,int r,int rt,int head,int tail,int x){
	if(head<=l&&r<=tail)return minx[rt]+=x,f[rt]+=x,void();
	int mid=(l+r)>>1;pushdown(rt);
	if(head<=mid)update(l,mid,rt<<1,head,tail,x);
	if(mid<tail)update(mid+1,r,rt<<1|1,head,tail,x);
	pushup(rt);
}
int query(){
	return minx[1];
}
int get(){
	int i,now=0,ans=0x3f3f3f3f;
	for(read(n,m),m--,i=1;i<=n;i++)read(a[i].l,a[i].r,a[i].w),a[i].r--;//就像我说的那样
	for(sort(a+1,a+1+n),i=1;i<=n;i++){
		while(now<=n&&query()==0)now++,now<=n?(a[now].l<=a[now].r?update(1,m,1,a[now].l,a[now].r,1):void()):void();//确保 now<=n
		if(now<=n)ans=min(ans,a[now].w-a[i].w);//如果 now>n 说明不可能完全覆盖了
		update(1,m,1,a[i].l,a[i].r,-1);//区间内所有点的覆盖的区间数都少了 1
	}
	return printf("%d",ans),0;
}
int main(){
	return get();
}

谢谢–zhengjun