题面
有 (m) 个染病的染病的村民，有 (n) 个治疗计划，((t_i,l_i,r_i,c_i)) 表示第 (t_i) 天晚上 ([l_i,r_i]) 的村民被治疗好，耗费 (c_i)。如果一个村民第 (i) 天早上染病，就会传染村民 (i-1) 和 (i+1)，求最小的代价，治疗所有的村民。
数据范围：(1le m,t_i,c_ile 10^9)，(1le nle 10^5)。
题解
狗的 (n) 和 (m) 与题目中的相反，且区间左闭右开，狗感觉这样更合适一些。
Subtask (2,3)
想象一下一张时间-村民的二维图，一个格子是黑色或白色，黑色表示染病。
可以发现，这个曲折的边界就是一条从图左端到右端的路径。
如果把每个治疗计划当作节点，题目就转化为了求点权最短路。
如果 (r_u-l_vge |t_u-t_v|)，有边 ((u,v))。
直接建图跑图时间复杂度 (Theta(n^2log n))，可以拿到 (35) 分。
Subtask (1,4)
势能线段树优化建图。
为什么能保证松弛次数为 (Theta(n))？
因为权在点上，如果用 dijkstra 堆优化，每个点进队一次即可，并且第一次得到的距离就是真距离。
所以可以建一棵势能线段树，维护两个值，分别解决 (v<u) 和 (v>u) 的情况。
线段树的下标是节点，维护的是限制值的最小值，每次连完边以后把维护值置为 (+infty)。
时间复杂度 (Theta(nlog n))。
代码
注意 (+infty) 的大小和 long long 的问题啊，啊啊啊，啊啊啊啊啊啊啊啊啊啊。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e5;
int m,n;
ll f[N];
struct info{
int t,l,r,c;
info(){}
info(int t,int l,int r,int c):
t(t),l(l),r(r),c(c){}
}a[N];
//Graph
/*
思考：什么时候 i 后面可以接 j？
a[i].r-a[j].l>=abs(a[i].t-a[j].t)
如果 a[j].t<a[i].t，要求就是
a[i].r-a[i].t>=a[j].l-a[j].t ->up
如果 a[j].t>a[i].t，要求就是
a[i].r+a[i].t>=a[j].l+a[j].t ->dn
这题有个关键点：权在点上，所以 dijkstra 可以爽一点
*/
vector<int> adj; // 记得清空
priority_queue<pair<ll,int>> q;
//SegmentTree
struct tree{
int l,r,mid,ma,mb; tree *ls,*rs;
tree(int l,int r):l(l),r(r),ma(iinf*2),mb(iinf*2){
if(r-l==1) return;
mid=(l+r)>>1,ls=new tree(l,mid),rs=new tree(mid,r);
}
void pushup(){
ma=min(ls->ma,rs->ma);
mb=min(ls->mb,rs->mb);
}
void fix(int i,int a,int b){
if(r-l==1) return ma=a,mb=b,void();
i<mid?ls->fix(i,a,b):rs->fix(i,a,b),pushup();
}
void adde(int x,int y,int mx,bool t){
if((t?ma:mb)>mx) return;
if(r-l==1) return ma=mb=iinf*2,adj.pb(l);
if(x<mid) ls->adde(x,y,mx,t);
if(y>mid) rs->adde(x,y,mx,t);
pushup();
}
};
//Function
//Main
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>m>>n;
R(i,n) cin>>a[i].t>>a[i].l>>a[i].r>>a[i].c,--a[i].t,--a[i].l;
sort(a,a+n,[&](info p,info q){return p.t<q.t;});
tree *rt=new tree(0,n);
R(i,n){
if(a[i].l==0) f[i]=a[i].c,
q.push(mp(-f[i],i)),rt->fix(i,iinf*2,iinf*2);
else rt->fix(i,a[i].l-a[i].t,a[i].l+a[i].t),f[i]=linf;
}
while(sz(q)){
int u=q.top().y; q.pop(),adj.clear();
rt->adde(0,u,a[u].r-a[u].t,true);
rt->adde(u+1,n,a[u].r+a[u].t,false);
for(int v:adj) f[v]=f[u]+a[v].c,q.push(mp(-f[v],v));
}
ll ns=linf;
R(i,n)if(a[i].r==m) ns=min(ns,f[i]);
if(ns==linf) ns=-1;
cout<<ns<<'
';
return 0;
}
祝大家学习愉快！