题解：P14255 列车（train）

· · 题解

题目传送门：P14255 列车。

思路

开往 OI 未来的列车能不能在这一年不要停开。

我们在这里定义修改操作为题目中的停开操作，查询操作为题目询问花费。

记 f_i 为第 i 个点能通过列车直接到达的点的编号最小值。

容易发现两个性质。

证明可以考虑反证法，这里不过多赘述。

接下来考虑如何动态维护 f 的值。

在一个修改操作中，显然 f 的值只会影响 l 到 r，在这中间的点的 f 最优只能为 r+1，那么相当于 f_i\leftarrow \max(f_i,r+1)。

在查询操作中，找到 f 在 1 到 l 间小于等于 r 的最大下标记为 x，由性质二，如果从小于等于 x 的位置开始，最优答案即为 \min_{i=1}^x (p_r-p_i)=p_r-p_x，对于大于 x 的位置，答案即为 \min_{i=x+1}^l (p_{f_i}-p_i)。

由 f 的性质二，用线段树和二分来维护这两种操作即可，没有什么细节，具体的可以查看代码。

希望大家能在 CSP-S 超长发挥，考出理想的成绩。

代码

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=1e5+10;
int n,m,a[N];
inline int read(){
    char c=getchar();
    int f=1,ans=0;
    while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
    while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
    return ans*f;
}
int mn[N<<2],t[N<<2],add[N<<2];//min a[f[i]]-a[i]
#define lc k<<1
#define rc k<<1|1
inline void pushup(int k){
    mn[k]=min(mn[lc],mn[rc]);
}
inline void pushdown(int k,int l,int r){
    if (add[k]){
        int x=add[k];
        add[lc]=add[rc]=t[lc]=t[rc]=x;
        int mid=l+r>>1;
        mn[lc]=a[x]-a[mid];
        mn[rc]=a[x]-a[r];
        add[k]=0;
    }
}
void build(int k,int l,int r){
    mn[k]=add[k]=0;
    if (l==r){
        mn[k]=a[l+1]-a[l];
        t[k]=l+1;
        return ;
    } 
    int mid=l+r>>1;
    build(lc,l,mid),build(rc,mid+1,r);
    pushup(k);
} 
void change(int k,int l,int r,int l1,int r1,int x){
    if (l1<=l&&r1>=r){
        mn[k]=a[x]-a[r];
        add[k]=t[k]=x;
        return ;
    }
    pushdown(k,l,r);
    int mid=l+r>>1;
    if (l1<=mid) change(lc,l,mid,l1,r1,x);
    if (r1>mid) change(rc,mid+1,r,l1,r1,x);
    pushup(k); 
}
int ask(int k,int l,int r,int x){
    if (l==r) return t[k];
    int mid=l+r>>1;
    pushdown(k,l,r);
    if (x<=mid) return ask(lc,l,mid,x);
    else return ask(rc,mid+1,r,x); 
}
int ask(int k,int l,int r,int l1,int r1){
    if (l1>r1) return 1e18;
    if (l1<=l&&r1>=r) return mn[k];
    int mid=l+r>>1,ans=1e18;
    pushdown(k,l,r);
    if (l1<=mid) ans=min(ans,ask(lc,l,mid,l1,r1));
    if (r1>mid) ans=min(ans,ask(rc,mid+1,r,l1,r1));
    return ans;
}
inline void solve1(int x,int y){ 
    int l=x,r=y,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if (ask(1,1,n,mid)<=y+1) ans=mid,l=mid+1;
        else r=mid-1; 
    } 
    if (ans==-1) return ;
    change(1,1,n,x,ans,y+1);
}
inline void solve2(int x,int y){
    int l=1,r=x,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if (ask(1,1,n,mid)<=y) ans=mid,l=mid+1;
        else r=mid-1;
    }
    int sum=1e18;
    if (ans!=-1) sum=min(sum,a[y]-a[ans]);
    if (ans==-1) ans=0;
    sum=min(sum,ask(1,1,n,ans+1,x));
    if (sum>1e16) puts("-1");
    else printf("%lld\n",sum);
}
inline void solve(){
    n=read(),m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    a[n+1]=1e18;
    build(1,1,n);
    while(m--){
        int op=read(),l=read(),r=read();
        if (op==1) solve1(l,r);
        else solve2(l,r);
    }
}
main(){
    int T=read();
    while(T--) solve();
    return 0;
}
//CSP-S 2025 RP++
//CSP-S 2025 RP++
//CSP-S 2025 RP++
//CSP-S 2025 RP++
//CSP-S 2025 RP++