【JOISC2020】治疗计划
Description
JOI 村庄有 \(N\) 个房屋，编号为 \(1\) 到 \(N\)，每个房屋住有一个村民，第 \(i\) 个房屋居住编号为村民 \(i\)。
现在，这 \(N\) 个房屋里的村民全部感染 COVILLAGE-19 病毒，有 \(M\) 个治疗方案被提出，第 \(i\) 个治疗方案描述为，在第 \(T_i\) 天的晚上，编号在 \([L_i,R_i]\) 区间内的村民被治愈。
COVILLAGE-19 病毒还会继续传播，在某天早上，如果村民 \(i\) 被感染，那么村民 \(i+1\) 和村民 \(i-1\) 也会被感染，因为病毒威力巨大，所以被治愈的村民有可能再次被感染。
您是 JOI 国的总理，您要选择一些方案使得 JOI 村庄所有村民全部被治愈，一天可以进行很多方案。
第 \(i\) 个方案要花费 \(C_i\)，求最小花费。
Input
第一行两个整数 \(N,M\) 代表村民数和方案数。
接下来 \(M\) 行每行四个整数 \(T_i,L_i,R_i,C_i\) 代表一个治疗方案。
Output
一行一个整数代表最小花费。
如果无法全部治愈，输出 \(-1\)。
Sample Input
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
Sample Output
7
Data Constraint
对于 \(100\%\) 的数据，\(1 \le N,T_i,C_i \le 10^9\)，\(1 \le M \le 10^5\)，\(1 \le L_i \le R_i \le N\)。
| 子任务 | 特殊性质 | 分数 |
|---|---|---|
| \(1\) | \(T_i=1\) | \(4\) |
| \(2\) | \(M \le 16\) | \(5\) |
| \(3\) | \(M \le 5000\) | \(30\) |
| \(4\) | 无 | \(61\) |
Solution
有一个还行的理解方法
画出一个时间-村民的二维图，描黑表示染病
一个治疗方案就是从左到右的路径
然后治疗方案之间的衔接就是斜率为\(1\)或\(-1\)的路径
然后可以考虑点权最短路
两个点\(i,j\)有边当且仅当\(R_i-L_j+1\ge |T_i-T_j|\)
由于是点权最短路，所以一个点在跑dij时，只会进队一次
考虑用线段树维护每个点的限制情况，每次用区间最小值判断是否能松弛
于是复杂度就是\(O(M\log M)\)了
Code
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define MX 2147483647
#define LL long long
#define N 100010
#define ls x<<1
#define rs (x<<1)|1
LL dis[N],inf,ans,D;
int n,m;
struct node{int T,l,r,c;}a[N];
struct point{
int x;LL y;
point(int _x,LL _y){x=_x;y=_y;}
bool operator<(const point&A)const{return y>A.y;}
};
priority_queue<point>q;
struct tree{
int Min[N*4][2];
void update(int x){F(i,0,1)Min[x][i]=min(Min[ls][i],Min[rs][i]);}
void change(int x,int l,int r,int pos,int v1,int v2){
if(l==r){Min[x][0]=v1;Min[x][1]=v2;return;}
int mid=l+r>>1;
pos<=mid?change(ls,l,mid,pos,v1,v2):change(rs,mid+1,r,pos,v1,v2);
update(x);
}
void query(int x,int l,int r,int ll,int rr,int val,int k){
if(r<ll||l>rr)return;
if(Min[x][k]>val)return;
if(l==r){
dis[l]=D+a[l].c;
q.push(point(l,dis[l]));
Min[x][0]=Min[x][1]=MX;
return;
}
int mid=l+r>>1;
query(ls,l,mid,ll,rr,val,k);query(rs,mid+1,r,ll,rr,val,k);
update(x);
}
void build(){F(i,1,m*4)Min[i][0]=Min[i][1]=MX;}
}t;
bool cmp(node x,node y){return x.T<y.T;}
int main(){
scanf("%d%d",&n,&m);
F(i,1,m)scanf("%d%d%d%d",&a[i].T,&a[i].l,&a[i].r,&a[i].c);
memset(dis,127,sizeof(dis));
ans=inf=dis[0];
sort(a+1,a+m+1,cmp);
F(i,1,m){
if(a[i].l==1){
t.change(1,1,m,i,MX,MX);
q.push(point(i,a[i].c));
dis[i]=a[i].c;
}else{
t.change(1,1,m,i,a[i].l-a[i].T,a[i].l+a[i].T);
}
}
while(!q.empty()){
point u=q.top();q.pop();D=u.y;
t.query(1,1,m,1,u.x-1,a[u.x].r-a[u.x].T+1,0);
t.query(1,1,m,u.x+1,m,a[u.x].r+a[u.x].T+1,1);
}
F(i,1,m)if(a[i].r==n)ans=min(ans,dis[i]);
printf("%lld",ans==inf?-1:ans);
return 0;
}