题意：
有 \(n\) 个行星，编号为 \(0\sim n-1\) 。
有 \(m\) 辆星际列车，第 \(i\) 辆列车在时刻 \(a_i\) 从行星 \(x_i\) 出发，在时刻 \(b_i\) 到达行星 \(y_i\) ，代价为 \(c_i\) 。换乘条件为上一辆车的终点和下一辆车的起点相同，且上一辆车到达时刻 \(\le\) 下一辆车出发时刻。
你需要吃 \(w\) 顿饭，第 \(i\) 顿饭必须在 \([l_i,r_i]\) 时刻吃。如果在列车上吃则免费，如果在 \(i\) 号行星吃则代价为 \(t_i\)。
时刻 \(0\) 时你在 \(0\) 号行星上，求到达 \(n-1\) 号行星的最小代价，如果无法到达输出 \(-1\) 。
\(2\le n\le 10^5,0\le m,w\le 10^5,0\le x_i\neq y_i\lt n,1\le a_i\lt b_i\le 10^9,1\le t_i,c_i\le 10^9,1\le l_i\le r_i\le 10^9\)。
时间限制 \(\texttt{1s}\) ，空间限制 \(\texttt{1000MB}\) 。
分析：
如果把行星、时刻二元组看成一个状态，容易发现状态很多，但是只有某辆列车的起始、终止状态是有用的。
令 \(f_i\) 为搭乘完第 \(i\) 辆列车的最小代价，容易写出转移方程：
\[f_i=\min\limits_{b_j\le a_i,y_j=x_i}f_j+g(b_j,a_i)\cdot t_{x_i}+c_i \]其中 \(g(x,y)\) 表示完全包含于区间 \((x,y)\) 的区间 \([l_i,r_i]\) 个数。
对起始、终止状态建立虚点，暴力跑上述转移，时间复杂度 \(\mathcal O(n^2)\)。
将所有列车按照 \(y_j\) 分类，每一类中按 \(b_j\) 升序排序，那么可以转移到 \(f_i\) 的是第 \(x_i\) 类中的一段前缀。
注意到转移代价 \(w(j,i)=g(b_j,a_i)\cdot t_i +c_i\) 满足四边形不等式（根据 \(g\) 的定义，交叉优于包含），因此 \(f\) 满足决策单调性。
使用二分队列优化，指针扫描加入所有 \(b_j\le a_i\) 的决策点，转移过程可以看我的笔记。
至于 \(g\) 的求法，只是一个简单的动态二维数点问题，用可持久化线段树维护。
时间复杂度\(\mathcal O(n\log^2n)\)。
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define lsh(x) (int)(lower_bound(e+1,e+k+1,x)-e)
using namespace std;
const int maxn=4e5+5;
const ll inf=1e18;
int k,tot;
int e[maxn],rt[maxn];
int hd[maxn],tl[maxn],px[maxn],py[maxn];
ll dp[maxn];
vi vec[maxn],vx[maxn],vy[maxn];
struct train
{
int a,b,c,x,y;
}d[maxn];
struct node
{
int ls,rs,sum;
}f[20*maxn];
struct oper
{
int x,l,r;
};
vector<oper> q[maxn];
void insert(int &p,int l,int r,int x)
{
f[++tot]=f[p],p=tot;
if(l==r) return f[p].sum++,void();
int mid=(l+r)>>1;
x<=mid?insert(f[p].ls,l,mid,x):insert(f[p].rs,mid+1,r,x);
f[p].sum=f[f[p].ls].sum+f[f[p].rs].sum;
}
int query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return f[p].sum;
if(!p||l>R||r<L) return 0;
int mid=(l+r)>>1;
return query(f[p].ls,l,mid,L,R)+query(f[p].rs,mid+1,r,L,R);
}
ll solve(int n,int m,int w,vi t,vi x,vi y,vi a,vi b,vi c,vi l,vi r)
{
for(int i=0;i<m;i++) e[++k]=a[i],e[++k]=b[i];
for(int i=0;i<w;i++) e[++k]=l[i],e[++k]=r[i];
sort(e+1,e+k+1);
k=unique(e+1,e+k+1)-e-1;
for(int i=0;i<m;i++) d[i+1]={lsh(a[i]),lsh(b[i]),c[i],x[i],y[i]};
for(int i=0;i<w;i++) vec[lsh(l[i])].push_back(lsh(r[i]));
for(int i=k;i>=1;i--)
{
rt[i]=rt[i+1];
for(auto p:vec[i]) insert(rt[i],1,k,p);
}
sort(d+1,d+m+1,[&](train u,train v){return u.a<v.a;});
d[++m]={k+1,k+2,0,n-1,n-1};
for(int i=0;i<=m;i++) vx[d[i].x].push_back(i),vy[d[i].y].push_back(i);
for(int i=0;i<n;i++)
{
hd[i]=1,tl[i]=0,q[i].push_back({0,0,0});
sort(vy[i].begin(),vy[i].end(),[&](int u,int v){return d[u].b<d[v].b;});
}
auto calc=[&](int j,int i)
{
return min(dp[j]+1ll*query(rt[d[j].b+1],1,k,1,d[i].a-1)*t[d[i].x]+d[i].c,inf);
};
for(int i=1;i<=m;i++)
{
int u=d[i].x,&h=hd[u],&t=tl[u],&j=py[u],k=px[u]++;
while(j<vy[u].size()&&d[vy[u][j]].b<=d[i].a)
{
while(h<=t&&calc(vy[u][j],vx[u][q[u][t].l])<=calc(q[u][t].x,vx[u][q[u][t].l])) t--;
if(t==q[u].size()-1) q[u].push_back({0,0,0});
if(h>t) q[u][++t]={vy[u][j],k,(int)vx[u].size()-1};
else
{
int l=max(k-1,q[u][t].l-1),r=q[u][t].r+1;
while(r-l>1)
{
int mid=(l+r)>>1;
calc(vy[u][j],vx[u][mid])<=calc(q[u][t].x,vx[u][mid])?r=mid:l=mid;
}
if(r<=vx[u].size()-1) q[u][t].r=r-1,q[u][++t]={vy[u][j],r,(int)vx[u].size()-1};
}
j++;
}
while(h<=t&&q[u][h].r<k) h++;
dp[i]=h<=t?calc(q[u][h].x,i):inf;
}
return dp[m]!=inf?dp[m]:-1;
}