线段树优化DP

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+5;
int n,l,r,mx,cnt;
LL f[N],ans = 6e9;
struct node
{
    int a,b,c;
} q[N];
bool cmp(node a,node b){ return a.b < b.b;}
struct Node
{
    int lf,rt;
    LL minv;
} t[N<<1];
// f[i]表示当前覆盖[L,i]需要的最小花费
// f[i] = min(f[i],f[j]+c[i])
// ai-1<=j<=bi-1
void pushup(int p)
{
    int x = t[p].lf,y = t[p].rt;
    t[p].minv = min(t[x].minv,t[y].minv);
}
void build(int p,int l,int r)
{
    if(l == r)
    {
        t[p].minv = f[l];
        return;
    }
    int mid = l+r>>1;
    t[p].lf = ++cnt; build(cnt,l,mid);
    t[p].rt = ++cnt; build(cnt,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int pos,LL d)
{
    if(l == r)
    {
        t[p].minv = d;
        return;
    }
    int mid = l+r>>1;
    if(pos <= mid) modify(t[p].lf,l,mid,pos,d);
    else modify(t[p].rt,mid+1,r,pos,d);
    pushup(p);
}
LL query(int p,int l,int r,int a,int b)
{
    if(a <= l && r <= b) return t[p].minv;
    int mid = l+r>>1;
    LL s = 6e9;
    if(a <= mid) s = min(s,query(t[p].lf,l,mid,a,b));
    if(b > mid) s = min(s,query(t[p].rt,mid+1,r,a,b));
    return s;
}
int main()
{
    cin>>n>>l>>r;
    l+=2; r+=2;
    for(int i = 1;i<=n;i++)
    {
        cin>>q[i].a>>q[i].b>>q[i].c;
        q[i].a+=2; q[i].b+=2;
        mx = max(mx,q[i].b);
    }
    sort(q+1,q+n+1,cmp);
    for(int i = l;i<=mx;i++) f[i] = 6e9;
    build(++cnt,1,mx);
    for(int i = 1;i<=n;i++)
    {
        f[q[i].b] = min(f[q[i].b],query(1,1,mx,q[i].a-1,q[i].b-1)+q[i].c);
        modify(1,1,mx,q[i].b,f[q[i].b]);
    }
    for(int i = r;i<=mx;i++) ans = min(ans,f[i]);
    if(ans == 6e9) ans = -1;
    cout << ans << '\n';
    return 0;
}