Acwing + 296 +清理班次2

设f[x]表示覆盖[l,r]需要花费的最小代价。

把所有的数据按b~i~从小到大排序，并除去要求区间之处的数据。

状态转移方程为：
$$ f[b_i]=min(f[b_i],\min\limits_{a_i-1\leq x<b_i}{{f[x]}}+c_i) $$
用线段树维护f[x]的最小值。初始值f[l-1]=0,即update(1,l-1,0)。

线段树建树时初始为无穷大。目标状态即可ask(1,r,r)。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct rec{
    int a,b,c;
    friend bool operator < (rec a,rec b) {
        return a.b<b.b; 
    }
}dat[maxn];
int tot,n,l,r ;
struct segtree{
    int l,r ; ll mi;
}t[maxn*4] ;
void build(int rt,int l,int r) {
    t[rt]=segtree{l,r,inf} ;
    if(l==r) {
        t[rt].mi=inf ;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2 ;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    t[rt].mi=min(t[rt*2].mi,t[rt*2+1].mi) ;
}
void update(int rt,int pos,ll v) {
    if(t[rt].l==t[rt].r) {
        t[rt].mi=min(t[rt].mi,v) ;
        return ;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    if(pos<=mid) update(rt*2,pos,v);
    else update(rt*2+1,pos,v) ;
    t[rt].mi=min(t[rt*2].mi,t[rt*2+1].mi) ; //pushup 
}
ll ask(int rt,int l,int r) { //查询最小值 
    if(t[rt].l>=l&&t[rt].r<=r) {
        return t[rt].mi;
    }
    int mid=(t[rt].l+t[rt].r)/2;
    ll ans=1ll<<32; 
    if(l<=mid) ans=min(ans,ask(rt*2,l,r) ) ;
    if(r>mid) ans=min(ans,ask(rt*2+1,l,r) ) ;
    return ans;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>l>>r; l+=2,r+=2;
    for(int i=1;i<=n;i++) {
        int a,b,c; cin>>a>>b>>c; a+=2,b+=2;
        if(a>r||b<l) continue ; //数据的简化
        a=max(a,l),b=min(r,b);
        dat[++tot]={a,b,c};
    }
    sort(dat+1,dat+1+tot); //从小到大   
    build(1,1,r) ;
    update(1,l-1,0); //init
    for(int i=1;i<=tot;i++) { //阶段 
        ll val=ask(1,dat[i].a-1,dat[i].b)+dat[i].c ; //决策 
        update(1,dat[i].b,val) ;
    }
    ll ans=ask(1,r,r) ;
    if(ans>=inf) cout<<-1;
    else cout<<ans; 
    return 0;
}