题解：P15163 [SWERC 2022] Crossing the Railways

· · 题解

首先考虑将移动方案在坐标 - 时间图上画出来，容易发现火车相当于竖直阻碍的墙，而合法方案就是一条折线，每段的斜率都 \geq v。

这里我们为了方便，给位置 0,m+1 分别加上一条 (0,s) 的火车，容易发现答案不变。

关键观察：最优的轨迹一定可以由以下线段组成：

因为任意的方案一定可以通过旋转或者平移的方式使它经过火车端点，而且这样一定最优。

:::info[为什么不用选火车左端点出发斜率为 v 的线段] 因为如果 (0,0) 出发的线段能到达左端点（忽略墙），那么左端点线段一定可以用 (0,0) 线段或两点连接线段代替，否则一定无法到达左端点。

那么如果 (0,0) 出发线段被某堵墙挡住了呢？那么一定是等待到右端点出发，而右端点出发的线段已经有了，左端点线段还是可以被代替或无解。

这样就只要维护 O(n^2) 条线段了，然后从左右端点开始分别扩展，即可找到线段不会被墙阻碍的区间，具体见代码。

然后就可以开始 dp 了，我们枚举每个位置区间 [i,i+1]，每个线段维护当前最少变速次数，然后把所有在这个区间内相交的线段转移。假设每个线段在 i 的时间为 a_i，在 i+1 的时间为 b_i，那么只要处理 a_i<a_j,b_i>b_j 的线段对，这个用 BIT 是好做的。

具体来说只要按 a_i 排序，把 b_i 后面的值取 \min 转移，然后把 dp 值加入 b_i，最后在逆着做一遍就行。

最后把所有在 m+1 时间在区间 [0,s] 内的答案取 \min 即可，时间复杂度 O(n^2m\log_2n)。

:::success[\texttt{code}]

//#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e5+10,B=27720,INF=0x3f3f3f3f3f3f3f3f;
struct node
{
    ll k,b,dn,up,dp;
    ll calc(ll x){return k*x+b;}
}li[N];
vector<node> L[20],now;
vector<pair<ll,ll>> row[20];
ll r[N],a[N],b[N],c[N],t[N];
ll n,m,s,v,tot,cnt,len;
bool check(ll i,ll d)
{
    auto it=lower_bound(row[i].begin(),row[i].end(),pair{d+1,0ll});
    if(it==row[i].begin()) return 1; it--;
    if(it->first<d&&it->second>d) return 0;
    return 1;
}
void add(ll k,ll b,ll up,ll dn)
{
    if(k<v) return;
    while(up<=m)
        if(check(up,k*up+b)) up++;
        else break;
    while(dn>=1)
        if(check(dn,k*dn+b)) dn--;
        else break;
    if(dn<=up) li[++tot]={k,b,dn,up,INF};
}
void init(ll nl)
{
    len=nl;
    for(int i=1;i<=len;i++) t[i]=INF;
}
void add(ll x,ll y)
{
    while(x<=len) t[x]=min(t[x],y),x+=x&(-x);
}
ll ask(ll x)
{
    ll res=INF;
    while(x) res=min(res,t[x]),x-=x&(-x);
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>s>>v; s*=B,v*=B;
    for(int i=1;i<=n;i++) 
        cin>>a[i]>>b[i]>>r[i],a[i]*=B,b[i]*=B;
    ++n,a[n]=0,b[n]=s,r[n]=0,++n,a[n]=0,b[n]=s,r[n]=m+1;
    for(int i=1;i<=n;i++) row[r[i]].push_back({a[i],b[i]});
    for(int i=1;i<=m;i++) sort(row[i].begin(),row[i].end());
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(r[i]<r[j])
            {
                ll k=(b[j]-a[i])/(r[j]-r[i]),b=a[i]-k*r[i];
                add(k,b,r[i],r[j]);
            }
    add(v,0,0,0);
    for(int i=1;i<=n;i++) add(v,b[i]-v*r[i],r[i],r[i]);
    for(int i=1;i<=tot;i++)
    {
        if(li[i].dn==0&&li[i].calc(0)>=0&&li[i].calc(0)<=s)
            li[i].dp=0;
        L[li[i].dn].push_back(li[i]);
    }
    for(int i=0;i<=m;i++)
    {
        vector<node> tmp; tmp.swap(now);
        for(auto it:tmp) if(it.up>i) now.push_back(it);
        for(auto it:L[i]) now.push_back(it); cnt=0;
        for(auto it:now) c[++cnt]=it.calc(i+1);
        sort(c+1,c+1+cnt),cnt=unique(c+1,c+1+cnt)-c-1;
        auto get=[&](ll x){return lower_bound(c+1,c+1+cnt,x)-c;};
        vector<ll> ord(now.size()),old(now.size());
        iota(ord.begin(),ord.end(),0);
        for(int i=0;i<now.size();i++) old[i]=now[i].dp;
        sort(ord.begin(),ord.end(),[&](ll a,ll b)
        {
            auto x=now[a],y=now[b];
            if(x.calc(i)==y.calc(i)) 
                return x.calc(i+1)>y.calc(i+1);
            return x.calc(i)<y.calc(i);
        });
        init(cnt);
        for(auto id:ord)
        {
            ll to=get(now[id].calc(i+1));
            now[id].dp=min(now[id].dp,ask(cnt-to+1)+1);
            add(cnt-to+1,old[id]);
        }
        sort(ord.begin(),ord.end(),[&](ll a,ll b)
        {
            auto x=now[a],y=now[b];
            if(x.calc(i)==y.calc(i)) 
                return x.calc(i+1)<y.calc(i+1);
            return x.calc(i)>y.calc(i);
        });
        init(cnt);
        for(auto id:ord)
        {
            ll to=get(now[id].calc(i+1));
            now[id].dp=min(now[id].dp,ask(to)+1);
            add(to,old[id]);
        }
    }
    ll ans=INF;
    for(auto it:now)
        if(it.calc(m+1)>=0&&it.calc(m+1)<=s)
            ans=min(ans,it.dp);
    cout<<(ans==INF?-1:ans);
    return 0;
}

:::