广播 题解

题目链接

广播
题目大意：区间上有个服务器，已知每个服务器的坐标和广播能力，求最好和最坏情况下需要让几个服务器发出信号能使所有服务器都收到信号。

思路

利用缩点的思想，考虑两个相邻的服务器，如果它们两个之间可以相互广播，就可以把它们看做一个服务器（也就是一个块），对于一个块只需要维护最左侧的服务器，最右侧的服务器，以及它的广播范围。
可以在输入的时候通过扫描在当前服务器左侧广播范围内的所有服务器来更新当前块，记录最坏情况（）。
这里有一个特判，如图：

如果扫描过程中出现一个服务器不可以广播到当前块，那么可以直接把这个服务器扔掉并记录下它对的贡献。
证明：
设当前更新的服务器块为。已知可以广播到，但是不能广播到。那么最坏情况下一定是先启动再启动，否则就会被启动，使得答案变小。
经过输入时对数据的处理，现在已经得到了所有服务器块。每一个块对应一个区间，那么对的计算就变成了简单的区间覆盖问题。只需要枚举每一个块，如果下一个块的大于当前的块的，就。并在每次枚举时都更新。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
using namespace std;
typedef long long ll;
const int N=1E6+10,INF=0x3f3f3f3f;
ll n,cnt,MAX,MIN;
struct Block{
	ll l,r,ld,rd;
}a[N];
inline ll read()
{
	ll ret=0,flag=1;char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')ret=ret*10+ch-'0',ch=getchar();
	return ret*flag;
}
int main()
{
	n=read();
	ll pos,dis;
	a[0]=(Block){INF,-INF,INF,-INF};
	rep(i,1,n)
	{
		pos=read();dis=read();
		ll lp=pos,lf=pos-dis,ri=pos+dis;
		while(pos-dis<=a[cnt].r)			//扫描前面所有在当前服务器广播范围内的块 
		{
			if(a[cnt].rd<lp)				//如果这个块不能广播到当前块，直接扔掉，维护MAX 
			{
				++MAX;
			}
			else							//能够相互广播，就更新当前块的值 
			{
				lp=a[cnt].l;
				lf=min(lf,a[cnt].ld);
				ri=max(ri,a[cnt].rd);
			}
			--cnt;							//继续找前面的块 
		}
		a[++cnt].r=pos;						//全部找完之后，把当前块加入到集合当中 
		a[cnt].l=lp;
		a[cnt].rd=ri;
		a[cnt].ld=lf;
	}
	MAX+=cnt;								//MAX等于删去的块+当前所有强连通的块 
	a[cnt+1]=(Block){INF,-INF,INF,-INF};
	ll ri=0;
	rep(i,1,cnt)
	{
		if(ri<a[i].l)
		++MIN;
		ri=max(ri,a[i].rd);					//求MIN 
	}
	cout<<MIN<<" "<<MAX<<endl;
}