题解 [JOISC2020] 治療計画

题解 [JOISC2020] 治療計画

题目链接

题意描述：

有一个长度为 \(n\) （下标由 \(1\sim n\)）的数轴， \(m\) 个操作，每个操作形如 \(t_i,l_i,r_i,c_i\) ，表示在第 \(t_i\) 个时刻覆盖区间 \(l_i\sim r_i\) ，费用为 \(c_i\) 。每过一个时刻，一个没有被覆盖的区间就会往左右延伸 \(1\) 个单位长度，求覆盖整个数轴的最小花费。
\(1\leq n,t_i,c_i\leq 10^9,m\leq 10^5,1\leq l_i\leq r_i\leq n\)

首先并不容易想到将数轴与时间放到二维平面上，操作抽象成直线 \(y=t_i\) 上的一段区间。将操作按 \(t_i\) 排个序，若区间 \(i,j(i 满足 \(r_i-l_j+1\geq |t_i-t_j|\) ，则连一条 \(r_i\to l_j\) 的边，答案即为从 \(y\) 轴到直线 \(x=n\) 的最短路。

暴力连边显然是 \(O(m^2\log{m})\) 的，考虑优化。

有关图论中边数过多的问题可以想到数据结构优化建图的套路， \(m\leq 10^5\) 的范围并不容易想到用线段树。

现在看回到限制条件：

分类讨论一下拆掉绝对值：

• 当 \(t_i\geq t_j\) 时， \(r_i-l_j+1\geq t_i-t_j\implies r_i-t_i+1\geq l_j-t_j\)
• 当 \(t_i\leq t_j\) 时， \(r_i-l_j+1\geq t_j-t_i\implies r_i+t_i+1\geq l_j+t_j\)

经历了[NOI2019]弹跳的自闭卡空间后，还是不建边好。于是可以对 \(l_i-t_i\) 和 \(l_i+t_i\) 分别建一棵线段树，最短路转移时在线段树上查询 \(1\sim i-1 /i+1\sim m\) ，若当前区间的最小值已经 \(>r_i-t_i+1/r_i+t_i+1\) 则直接return，否则暴力向下松弛即可。这样显然是一棵势能线段树，复杂度为 \(\Theta(m\log^2{m})\)。

代码如下：

#include
#define int long long
#define inf 1e15
#define INF 0x3f3f3f3f
#define N 100005
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair
#define il inline
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
il int read(){
	int w=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
	while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
	return w*h;
}
struct Plan{
	int l,r,t,c;
	bool operator<(const Plan&p)const{return tq;
namespace SGT{
	int Min[N<<2][2];
	void Pushup(int k){
		Min[k][0]=min(Min[ls][0],Min[rs][0]);
		Min[k][1]=min(Min[ls][1],Min[rs][1]);
	}
	void Build(int k,int l,int r){
		if(l==r){
			Min[k][0]=a[l].l-a[l].t;
			Min[k][1]=a[l].l+a[l].t;
			return;
		}
		Build(ls,l,mid);
		Build(rs,mid+1,r);
		Pushup(k);
	}
	void Query(int k,int l,int r,int x,int y,int val,int dist,int ty){
		if(Min[k][ty]>val)return;
		if(l==r){
			if(dist+a[l].c=x&&r<=y){
			Query(ls,l,mid,x,y,val,dist,ty);
			Query(rs,mid+1,r,x,y,val,dist,ty);
			Pushup(k);
			return;
		}
		if(x<=mid)Query(ls,l,mid,x,y,val,dist,ty);
		if(mid