首先有个暴力DP，设$s_i=\sum\limits_{j\geq i}w_j$，有$f_i=\min\limits_{l_i\lt j\leq i}f_{j-1}+s_{i+1}\max\{t_{j\cdots i}\}$

想用斜率优化，但是式中的max会随$i$改变而改变

考虑把单调栈的弹栈序列建成一棵树，每个点$x$存的直线为$y=t_xx+\min\{f_{fa_x+1\cdots x}\}$，这样一个点要查的直线就是到根路径的一条链，$l_i$的限制在最后一小段查$f$的区间最小值即可

这棵树有很好的性质，从根往下走的$t_x$是不升的，我们要查的$s_{i+1}$是递减的，所以可以树剖+线段树维护凸壳，边插入边维护即可

总时间复杂度$O(n\log^2n)$，感觉把单调栈建成树这一步非常厉害

#include
     
      #include
      
       using namespace std;typedef long long ll;typedef double du;const ll inf=1e18;void fmin(ll&a,ll b){	if(b
       
        siz[k])k=to[i];	}	son[x]=k;}int bl[100010],pos[100010],rp[100010];void dfs(int x,int chain){	bl[x]=chain;	pos[x]=++M;	rp[M]=x;	if(~son[x])dfs(son[x],chain);	for(int i=h[x];i;i=nex[i]){		if(to[i]!=son[x])dfs(to[i],to[i]);	}}struct line{	ll k,b;	line(ll k=0,ll b=0):k(k),b(b){}	ll v(ll x){return k*x+b;}};du its(line a,line b){	return(b.b-a.b)/(du)(a.k-b.k);}typedef vector
        
          vl;vl g[400010];#define ls g[g.size()-1]void push(vl&g,line v){	if(!g.empty()&&ls.k==v.k){		if(ls.b<=v.b)return;		g.pop_back();	}	while(g.size()>1&&its(ls,g[g.size()-2])>=its(ls,v))g.pop_back();	g.push_back(v);}void modify(int p,line v,int l,int r,int x){	push(g[x],v);	if(l==r)return;	int mid=(l+r)>>1;	if(p<=mid)		modify(p,v,l,mid,x<<1);	else		modify(p,v,mid+1,r,x<<1|1);}ll get(vl&g,ll v){	while(g.size()>1&&its(ls,g[g.size()-2])>=v)g.pop_back();	return ls.v(v);}ll query(int L,int R,ll v,int l,int r,int x){	if(L<=l&&r<=R)return get(g[x],v);	int mid=(l+r)>>1;	ll res=inf;	if(L<=mid)fmin(res,query(L,R,v,l,mid,x<<1));	if(mid
         
          <<1|1));	return res;}ll f[100010];ll T[400010];int N;void build(){	for(N=1;N<=n+1;N<<=1);	for(int i=1;i
          
           <<1;i++)T[i]=inf;}void modify(int x,ll v){ T[x+=N]=v; for(x>>=1;x;x>>=1)T[x]=min(T[x<<1],T[x<<1|1]);}ll query(int s,int t){ ll res=inf; for(s+=N-1,t+=N+1;s^t^1;s>>=1,t>>=1){ if(~s&1)fmin(res,T[s^1]); if(t&1)fmin(res,T[t^1]); } return res;}void work(int x){ int u,l,r,mid; ll res; modify(x,f[x-1]); modify(pos[x],line(t[x],query(fa[x]+1,x)),1,M,1); res=inf; for(u=x;;){ if(::l[x]>fa[bl[u]]){ l=pos[bl[u]]; r=pos[u]; while(l
           
            >1; if(rp[mid]>=::l[x]) r=mid; else l=mid+1; } if(pos[u]>l)fmin(res,query(l+1,pos[u],s[x+1],1,M,1)); u=rp[l]; break; }else{ fmin(res,query(pos[bl[u]],pos[u],s[x+1],1,M,1)); u=fa[bl[u]]; } } fmin(res,query(::l[x],u)+t[u]*s[x+1]); f[x]=res;}int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d%d",l+i,t+i,w+i); l[i]++; } for(i=n;i>0;i--)s[i]=s[i+1]+w[i]; for(i=1;i<=n;i++){ while(tp&&t[i]>t[st[tp]]){ add(st[tp-1],st[tp]); tp--; } st[++tp]=i; } for(i=1;i<=tp;i++)add(st[i-1],st[i]); dfs(0); M=0; dfs(0,0); fa[0]=-1; build(); for(i=1;i<=n;i++)work(i); printf("%lld",f[n]);}