题解：P14255 列车（train）

Hisy · 2025-10-19 17:31:53 · 题解

前言

比赛时调了半天的代码，赛后发现男孩只是少判了边界就被活活 Hack 掉了 100pts。

分析

根据题意可以发现，整个火车系统可以理解为 n^2 个点，每一次操作为：

• 把 x\in[l,r],y\in[l,r] 的点之间道路全部删除。
• 查询从 x 到 y 的最短路。

容易想到一个性质，即为只需要找到一趟列车即可。若有转乘点 d_1,d_2\cdots d_k，则有 P=p_r-p_k+p_k-p_{k-1}\cdots-p_1+p_1-p_l=p_r-p_l，在一趟列车可以到达的情况下所有方案均是等价的。

所以我们的操作变为了：初始时有 \frac{n\times(n-1)}{2} 个区间，[l,r](1\le l<r\le n)：

• 删除 [l,r]([l,r]\in[x,y])。
• 查询最小（价值）的 [l,r] 使 [l,r] 没被删除且 [x,y]\in[l,r]。

这个该怎么维护呢？可以考虑一种类似于挂链或者并查集的方式：记 pre_i 表示 i 之前最后一个没有停开的点，即 pre_i 为最后一个可以直达 i 的点。

所以操作变为了初始时 pre_i=i，有：

• 每次将 [x,y] 内的数值修改为上一个版本的 pre_{x-1}。
• 查询 \min_{x\le mid<y}(p_r-p_{pre_{mid}})。

第二个查询操作里面有 p_{pre_{mid}}，看上去较难维护，但是发现 pre 总是连续一段（或者单个出现），因为每一次删除 pre_i 只能够比之前变得更前。

但是这还不足以维护，但是 pre 其实还有单调性：

• 初始时，pre_i=i>pre_{i-1}。
• 修改时，pre_i=pre_{l-1}\le pre_{i+1}。

所以对于这个可以直接查找最后一个 pre_i\le r 的点转移。

代码

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
typedef long long ll;
const ll INF=1e15;
int n,m;
ll p[MAXN];
struct SegementTree{
    struct node{
        ll val;
        int low,tag;
    }tree[MAXN<<2];
    inline void push_up(int root){
        tree[root].val=min(tree[root<<1].val,tree[root<<1|1].val);
        tree[root].low=min(tree[root<<1].low,tree[root<<1|1].low); 
    }
    inline int push_down(int root,int l,int r){
        int mid=(l+r)>>1;
        if(tree[root].tag==-1){
            return mid;
        }
        tree[root<<1].tag=tree[root<<1].low=tree[root].tag;
        tree[root<<1].val=p[tree[root].tag]-p[mid];
        tree[root<<1|1].tag=tree[root<<1|1].low=tree[root].tag;
        tree[root<<1|1].val=p[tree[root].tag]-p[r];
        tree[root].tag=-1;
        return mid;
    }
    inline void build(int root,int l,int r){
        tree[root].tag=-1;
        if(l==r){
            tree[root].low=l+1;
            tree[root].val=p[l+1]-p[l];
            return;
        } 
        int mid=(l+r)>>1;
        build(root<<1,l,mid);
        build(root<<1|1,mid+1,r);
        push_up(root);
    }
    inline void change(int root,int l,int r,int L,int R,int val){
        if(L<=l&&r<=R){
            tree[root].tag=tree[root].low=val;
            tree[root].val=p[val]-p[r];
            return;
        }
        int mid=push_down(root,l,r);
        if(L<=mid){
            change(root<<1,l,mid,L,R,val);
        }
        if(mid<R){
            change(root<<1|1,mid+1,r,L,R,val);
        }
        push_up(root);
    }
    inline int find(int root,int l,int r,int val){
        if(l==r){
            return l*(tree[root].low<=val);
        }
        int mid=push_down(root,l,r);
        if(tree[root<<1|1].low<=val){
            return find(root<<1|1,mid+1,r,val);
        }
        return find(root<<1,l,mid,val);
    }
    inline ll query(int root,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            return tree[root].val;
        }
        int mid=push_down(root,l,r);
        if(L>mid){
            return query(root<<1|1,mid+1,r,L,R);
        }
        if(mid>=R){
            return query(root<<1,l,mid,L,R);
        }
        return min(query(root<<1,l,mid,L,R),query(root<<1|1,mid+1,r,L,R));
    }
    inline void print(int root,int l,int r){
        if(l==r){
            printf("{%d %lld} ",tree[root].low,tree[root].val);
            return;
        }
        int mid=push_down(root,l,r);
        print(root<<1,l,mid);
        print(root<<1|1,mid+1,r);
    }
}Tree;
inline void solve(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&p[i]);
    }
    p[0]=-INF;
    p[n+1]=INF;
    Tree.build(1,1,n);
    while(m--){
//      Tree.print(1,1,n);
//      putchar('\n');
        int opt,x,y;
        scanf("%d %d %d",&opt,&x,&y);
        if(opt==1){
            int pos=min(y,Tree.find(1,1,n,y+1));
//          cout<<pos<<endl;
            if(pos>=x){
                Tree.change(1,1,n,x,min(pos,y),y+1);
//              cout<<x<<" "<<min(pos,y)<<" "<<y+1<<endl;
            }
        }else{
            int pos=min(x,Tree.find(1,1,n,y));
//          cout<<y<<":"<<pos<<endl;
            ll ans=INF;
            if(pos>=1){
                ans=min(ans,p[y]-p[pos]);
            }
            if(pos<x){
                ans=min(ans,Tree.query(1,1,n,pos+1,x));
            }
            if(ans>p[n]-p[1]){
                ans=-1;
            }
            printf("%lld\n",ans);
        }
    }
}
signed main(){
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}