与上一题类似.
还是设f[i]表示清理到i的最小花费(不可能则为无穷大)
那么对于每一条线段,有如下转移:
$$f[b_i]=min(f[b_i],min _{j=a_i-1}^{b_i} f[j]+c_i)$$
直接暴力做时间复杂度是$O(n^2)$
而显然查询的$min_{j=a_i-1}^{b_i} f[j]+1$是区间最值.
对$[start,end]$建一棵单点修改,区间求最值的线段树维护一下就好了.
注意到start可能$=0,start-1$可能会出点问题,不妨把整个区间都右移一个单位.
时间复杂度$O(nlogn)$
/**********/省略快读
#define MAXN 200011
ll n,start,end;
struct Segment_Tree
{
ll t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
void pushup(un num)
{
rt=min(tl,tr);
}
void build(un l=0,un r=end,un num=1)
{
if(l==r)
{
rt=INF;
return;
}
un mid=(l+r)>>1;
build(l,mid,num<<1);build(mid+1,r,num<<1|1);
pushup(num);
}
void modify(un p,ll val,un l=0,un r=end,un num=1)
{
if(l==r)
{
if(l==p)rt=val;
return;
}
un mid=(l+r)>>1;
if(p<=mid)modify(p,val,l,mid,num<<1);
else modify(p,val,mid+1,r,num<<1|1);
pushup(num);
}
ll Qmin(un ql,un qr,un l=0,un r=end,un num=1)
{
if(ql<=l&&r<=qr)return rt;
ll ans=INF;
un mid=(l+r)>>1;
if(ql<=mid)umin(ans,Qmin(ql,qr,l,mid,num<<1));
if(qr>mid)umin(ans,Qmin(ql,qr,mid+1,r,num<<1|1));
return ans;
}
}sgt;
struct Seg
{
ll l,r,c;
bool operator <(const Seg& t)
const
{
return r<t.r;
}
}a[MAXN];
int main()
{
n=read(),start=read()+1,end=read()+1;
for(ll i=1;i<=n;++i)
{
a[i].l=read()+1,a[i].r=read()+1;
a[i].c=read();
}
std::sort(a+1,a+n+1);
sgt.build();
sgt.modify(start-1,0);
for(ll i=1;i<=n;++i)
{
ll minv=min(sgt.Qmin(a[i].l-1,a[i].r)+a[i].c,sgt.Qmin(a[i].r,a[i].r));
sgt.modify(a[i].r,minv);
}
ll ans=sgt.Qmin(end,end);
printf("%lld",ans==INF?-1:ans);
return 0;
}