P7214治疗计划

把未感染和感染抽象为 0/1，那么原问题可以转化为初始有一个全为$1$ 的序列，可以在特定时间进行一次区间覆盖操作（有代价），$1$ 会向左右扩散，问能不能将整个序列全部覆盖为 0 且使得操作代价最小。

对于选择区间进行覆盖的问题，这一类经典问题有一种状态设计就是设$f(i)$ 表示将$[1,i]$ 这个前缀进行覆盖的最小代价。但是问题在于这样转移是$O(nm)$ 的不太好搞，考虑这个$m$ 的瓶颈就是在于我们需要知道每一个覆盖区间右端点在哪里。考虑切换一下 dp 状态，设$f(i)$ 表示将$[1,r_i]$ 覆盖的最小代价，转移通过$t$ 的偏序关系进行转移：

$$\begin{aligned}f(i) & \leftarrow f(j)+c_i & r_j -l_i+1 \ge |t_i -t_j| \end{aligned}$$

时间复杂度还是$O(nm)$，无敌了。而且还自带两个偏序关系更是逆天。但是观察这个 DP 是一个类似于最短路形式的转移（说人话就是转移代价只和目标的代价有关），考虑用 Dijkstra 优化这个 DP。让后绝对值可以通过对$t$ 排序去掉，对于转移可以用线段树优化这个最小值转移，势能分析有时间复杂度$O(n \log n)$。

这个题目有一个巨大的卡阻就是在于 DP 容易选择会以时间作为主体，这样的话你无论怎么都无法优化掉时间这一维。一开始想的就是$f(i,j)$ 添加了时间$j$ 这一个维度，但是发现这个枚举时间反而成为了瓶颈。这个时候，我们需要分析，我们知道什么就够了。分析下来$j$ 反而可以从转移中天然的去掉，这样我们就做到了优化 DP 的过程。

#include<bits/stdc++.h>
#include <queue>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=5e5+15,INF=1e18;
struct Node{
    int l,r,c,t;
}a[MN];
int n,m,f[MN],ans=INF;
bool vis[MN];
priority_queue<pir,vector<pir>,greater<pir>> q;

struct Segment{
    #define ls p<<1
    #define rs p<<1|1
    struct Node{
        int l,r,mn[2];
    }t[MN<<2];

    void pushup(int p){
        t[p].mn[0]=min(t[ls].mn[0],t[rs].mn[0]);
        t[p].mn[1]=min(t[ls].mn[1],t[rs].mn[1]);
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        t[p].mn[0]=t[p].mn[1]=INF;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
    }

    void modify(int p,int pos,int x,int y){
        if(t[p].l==t[p].r){
            t[p].mn[0]=x-y;
            t[p].mn[1]=x+y;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=pos) modify(ls,pos,x,y);
        else modify(rs,pos,x,y);
        pushup(p);
    }

    void update(int p,int fl,int fr,int op,int v,int w){
        if(t[p].mn[op]>v) return;
        if(t[p].l==t[p].r){
            f[t[p].l]=w+a[t[p].l].c;
            q.push(pir(f[t[p].l],t[p].l));
            t[p].mn[0]=t[p].mn[1]=INF;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) update(ls,fl,fr,op,v,w);
        if(mid<fr) update(rs,fl,fr,op,v,w);
        pushup(p);
    }

    #undef ls
    #undef rs
}sg;

bool cmp(Node x,Node y){
    return x.t<y.t;
}

void dijkstra(){
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=m;i++){
        if(a[i].l==1){
            f[i]=a[i].c;
            q.push(pir(f[i],i));
            sg.modify(1, i, INF, 0);
        }else sg.modify(1, i, a[i].l, a[i].t);
    }
    while(!q.empty()){
        auto fr=q.top();
        q.pop();
        int u=fr.second;
        if(vis[u]) continue;
        vis[u]=1;
        sg.update(1,1,u-1,0,a[u].r-a[u].t+1,f[u]);
        sg.update(1,u+1,m,1,a[u].r+a[u].t+1,f[u]);
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].t>>a[i].l>>a[i].r>>a[i].c;
    }
    sort(a+1,a+1+m,cmp);
    sg.build(1,1,m);
    dijkstra();
    for(int i=1;i<=m;i++){
        if(a[i].r==n){
            ans=min(ans,f[i]);
        }
    }
    if(ans>=INF) cout<<-1;
    else cout<<ans;

    return 0;
}