P14255 列车（train）题解

Lyz09 · 2025-10-18 20:07:49 · 题解

出题人题解。

解法 1

暴力维护每趟列车的状态，查询暴力枚举每趟列车。

时间复杂度 O(Tmn^2)，期望通过测试点 1\sim 3。

解法 2

下文以列车 [l,r] 表示以 l 为起点站、r 为终点站的列车。

若列车 [l,r] 被停开，则列车 [l+1,r] 和列车 [l,r-1] 一定被停开。

若列车 [l,r] 没有被停开，则列车 [l-1,r] 和列车 [l,r+1] 一定没有被停开。

也就是说如果固定起点站/终点站，列车是否被停开关于它的终点站/起点站具有单调性。所以我们可以对于每个 i 维护 f_i 表示列车 [k_1,i] （k_1> f_i）均已被停开，列车 [k_2,i]（k_2\leq f_i）均未被停开。

停开事件相当于对于 x_i\leq k\leq y_i 的 k 进行 f_k\leftarrow \min(f_k,x_i-1)。查询事件则遍历每个右端点，查询搭乘列车 [\min(x_i,f_j),\max(y_i,j)] 的代价的最小值。

时间复杂度 O(Tmn)，期望通过测试点 1\sim 7。

解法 3

对于每次停开事件令 f_{y_i}\leftarrow \min(f_{y_i},x_i-1)，所有停开事件完成之后依次从 n-1\sim 1 遍历 i，且令 f_{i}\leftarrow \min(f_i,f_{i+1})，这样就省去了解法 2 中停开事件的遍历修改。

对于查询事件，考虑列车 [f_j,j] 对于 x_i,y_i 的贡献，可以分为三类：

因为当 i 增大时，f_i 单调不降（维护的最后一步为 f_{i}\leftarrow \min(f_i,f_{i+1})），所以以上三类列车 [f_i,i] 的 i 在值域上三个不交的区间，可以使用二分等状物找到区间的界限，并用 ST 表区间查询。

时间复杂度 O(T(n+m)\log n)，期望通过测试点 8\sim 10。

解法 4

考虑查询时不枚举 f_i=f_{i+1} 的 i，令大于 i_0 最小的被枚举到的 i 为 i_1，则一定有 f_{i_1}\geq i_0-1。

对于贡献为第 1 类或第 3 类的列车 [f_i,i]，显然只有 f_i 最大/ i 最小的列车 [f_i,i] 才能去到该类列车的最小代价。对于第 2 类列车只有 O(1) 个，因此对于单次查询事件总的有用的列车个数是 O(1) 级别的，直接枚举即可。

时间复杂度 O(T(n+m)\log n)，期望通过测试点 11,12。

解法 5

因为后面的停开事件的列车范围是包含前面的停开事件的，因此查询事件只需要考虑在此之前最后一次停开事件即可。

时间复杂度 O(T(n+m))，期望通过测试点 13,14。

解法 6

考虑去掉列车范围被包含的停开事件，可以使用珂朵莉树在线维护范围互不包含的列车 [f_i,i]。

第 1 类列车和第 3 类列车可以根据解法 4 中的结论快速找到对应的唯一的列车，第 2 类列车可以暴力枚举贡献。

当 x_i,y_i 随机时一次查询事件的 x_i,y_i 期望并不会被很多列车 [f_i,i] 所包含，可以直接遍历。

时间复杂度 O(T(n+mc)\log n)，其中 c 是一次查询事件的 x_i,y_i 被列车 [f_i,i] 包含的列车个数，期望通过测试点 1\sim 7 以及 11\sim 18。

解法 7

考虑使用线段树维护 f_i，因为对于任意时刻有 f_i\leq f_{i+1}，所以每次可以在线段树上暴力取 min（若当前区间 f_i 最大值小于等于取 min 的值则直接退出，若当前区间 f_i 最小值大于等于取 min 的值则区间赋值），维护每个 i 的 p_{i}-p_{f_i}，以及区间 p_{i}-p_{f_i} 的 min。

可以通过线段树上二分找出解法 3 中三类列车的分界点，在线段树上分别查询区间 p_i-p_{f_i} 的 min 以及单点 f_i 的值即可。

时间复杂度 O(T(n+m)\log n)，期望通过测试点 1\sim 25。

这个题还有别的做法，例如 ODT+线段树、分块等，不过这些都是我一开始没有预料到的。

对于本题被卡常数的选手我感到抱歉，一个方面是 cz 说下发文件不能太大，因此 n 大的数据 T 没有给满导致部分选手以为自己跑得很快，另一方面是有验题人写了个平方解法冲过了所有点，为了卡这个做法写了半天 Gen 也只卡到了 2.0s 左右，再加上 std 跑了 550ms，验题人中最慢的也只跑了 1.1s，因此开了 1.5s。但是如果平方过题就成追忆了。

有人没发现 f_i 有单调性以为必须要吉司机才能做，我不说是谁（

::::success[我的代码]

#include<iostream>
using namespace std;
#define N 100010
int t,n,m,p[N];
class sgtree
{
    public:
        #define sN 400010
        int mi[sN],ma[sN],val[sN],tag[sN];
        void build(int o,int l,int r)
        {
            tag[o]=1000000000;
            if(l==r)
            {
                mi[o]=ma[o]=p[l];
                val[o]=0;
                return;
            }
            int mid=l+r>>1;
            build(o<<1,l,mid);
            build(o<<1|1,mid+1,r);
            mi[o]=min(mi[o<<1],mi[o<<1|1]);
            ma[o]=max(ma[o<<1],ma[o<<1|1]);
            val[o]=min(val[o<<1],val[o<<1|1]);
        }
        void pushdown(int o,int l,int r)
        {
            if(tag[o]>=1000000000)
             return;
            int mid=l+r>>1;
            tag[o<<1]=tag[o];
            mi[o<<1]=ma[o<<1]=tag[o];
            val[o<<1]=p[l]-tag[o];
            tag[o<<1|1]=tag[o];
            mi[o<<1|1]=ma[o<<1|1]=tag[o];
            val[o<<1|1]=p[mid+1]-tag[o];
            tag[o]=1000000000;
        }
        void update(int o,int l,int r,int x,int y,int k)
        {
            if(l>y||r<x)
             return;
            if(k>=ma[o])
             return;
            if(l>=x&&r<=y&&k<=mi[o])
            {
                tag[o]=k;
                mi[o]=ma[o]=k;
                val[o]=p[l]-k;
                return;
            }
            pushdown(o,l,r);
            int mid=l+r>>1;
            update(o<<1,l,mid,x,y,k);
            update(o<<1|1,mid+1,r,x,y,k);
            mi[o]=min(mi[o<<1],mi[o<<1|1]);
            ma[o]=max(ma[o<<1],ma[o<<1|1]);
            val[o]=min(val[o<<1],val[o<<1|1]);
        }
        int querybound(int k,int n)
        {
            if(ma[1]<=k)
             return n;
            int o=1,l=1,r=n,ans=0;
            while(l<r)
            {
                pushdown(o,l,r);
                int mid=l+r>>1;
                if(ma[o<<1]<=k)
                {
                    l=mid+1;
                    o=(o<<1|1);
                }
                else
                {
                    r=mid;
                    o=(o<<1);
                }
            }
            return l-1;
        }
        int queryone(int o,int l,int r,int x)
        {
            if(l==r)
             return mi[o];
            pushdown(o,l,r);
            int mid=l+r>>1;
            if(x<=mid)
             return queryone(o<<1,l,mid,x);
            else
             return queryone(o<<1|1,mid+1,r,x);
        }
        int querymival(int o,int l,int r,int x,int y)
        {
            if(l>y||r<x)
             return 1000000000;
            if(l>=x&&r<=y)
             return val[o];
            pushdown(o,l,r);
            int mid=l+r>>1;
            int q1=querymival(o<<1,l,mid,x,y);
            int q2=querymival(o<<1|1,mid+1,r,x,y);
            return min(q1,q2);
        }
}tr;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n>100000||m>100000)
         exit(111);
        p[0]=-1000000000;
        for(int i=1;i<=n;i++) 
        {
            cin>>p[i];
            if(p[i]<=p[i-1])
             exit(112);
        }
        tr.build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int opt,x,y;
            cin>>opt>>x>>y;
            if(opt<1||opt>2)
             exit(113);
            if(x<1||x>y||y>n)
             exit(114);
            if(opt==1)
            {
                tr.update(1,1,n,x,y,p[x-1]);
            }
            else
            {
                int ans=1000000000;
                int h=tr.querybound(p[x]-1,n);
                if(h<y)
                {
                    cout<<p[y]-p[x]<<"\n";
                    continue;
                }
                ans=min(ans,tr.querymival(1,1,n,y,h));
                if(h<n)
                 ans=min(ans,p[h+1]-p[x]);
                if(ans<=p[n]-p[1])
                 cout<<ans<<"\n";
                else
                 cout<<-1<<"\n";
            }
        }
    }
}

::::