题解：P14255 列车（train）

· · 题解

好题，质量很高。

思路

首先是一些不成熟的想法，考虑对于一个城市 i 来说，我们用 L_i 表示其左边距离其最近的一个有直达 i 车站车次的城市编号（即满足没有操作一覆盖 [L_i,i]），同理我们也可以定义出 R_i 表示其右边距离其最近的一个有直达 i 车站车次的城市编号（即满足没有操作一覆盖 [i,R_i]）。

简单分析即可发现，L_i 与 R_i 都是单调不降的，而对于操作一，就相当于 [x,y] 区间中的 L_i 对 x-1 取 \min，R_i 对 y+1 取 \max，这一部分直接丢到线段树上维护即可。

此时对于一次询问来说，直接乘坐 [L_y,y] 列车和 [x,R_x] 列车一定会比乘坐的车站端点在 L_y,R_x 之外的所有车次要优，但是有可能最优车次的右端点位于 [y,R_x] 之间，怎么办呢？

对于一个城市 u\in[y,R_x]，其 L_u 一定是小于等于 x 的，所以如果我要做一趟以 u 作为右端点的车次，则我的花费最小为 p_u-p_{L_u}。

那么我们只需要维护出 p_u-p_{L_u} 的区间最小值即可，由于 L_u 单调，所以区间取 \min 操作可以通过线段树上二分变成区间赋值，而如果是区间赋值的话我们就可以维护 p_u-p_{L_u} 的最小值了。

于是你就做完了这一题，时间复杂度 O(Tm\log n)。

代码

#include <iostream>
#include <algorithm>
#define ll int
#define lc (x<<1)
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const ll N=1e5+10;
const ll INF=1e9;
ll n,m,pls[N];
ll RsL[N<<2],LsR[N<<2],tag1[N<<2],tag2[N<<2];
ll dat1[N<<2],maxx[N<<2];
void push_up1(ll x){
    RsL[x]=min(RsL[lc],RsL[rc]);
    dat1[x]=min(dat1[lc],dat1[rc]);
    maxx[x]=max(maxx[lc],maxx[rc]);
}
void push_down1(ll x,ll l,ll r){
    if(tag1[x]==INF) return;
    dat1[lc]=pls[l]-pls[tag1[x]];dat1[rc]=pls[mid+1]-pls[tag1[x]];
    tag1[lc]=tag1[rc]=RsL[lc]=RsL[rc]=maxx[lc]=maxx[rc]=tag1[x];
    tag1[x]=INF;
}
void build1(ll x,ll l,ll r){
    tag1[x]=INF;
    if(l==r){maxx[x]=RsL[x]=l;dat1[x]=0;return;}
    build1(lc,l,mid),build1(rc,mid+1,r);push_up1(x);
}
void chg1(ll x,ll l,ll r,ll L,ll R,ll v){
    if(maxx[x]<=v) return;
    if(L<=l&&r<=R&&v<=RsL[x]){
        maxx[x]=RsL[x]=tag1[x]=v;
        dat1[x]=pls[l]-pls[v];
        return;
    }
    push_down1(x,l,r);
    if(L<=mid) chg1(lc,l,mid,L,R,v);
    if(R>mid) chg1(rc,mid+1,r,L,R,v);
    push_up1(x);
}
ll query1(ll x,ll l,ll r,ll p){
    if(l==r) return RsL[x];
    push_down1(x,l,r);
    if(p<=mid) return query1(lc,l,mid,p);
    return query1(rc,mid+1,r,p);
}
ll getmin1(ll x,ll l,ll r,ll L,ll R){
    if(L<=l&&r<=R) return dat1[x];
    ll ret=INF;push_down1(x,l,r);
    if(L<=mid) ret=min(ret,getmin1(lc,l,mid,L,R));
    if(R>mid) ret=min(ret,getmin1(rc,mid+1,r,L,R));
    return ret; 
}
void push_up2(ll x){LsR[x]=max(LsR[lc],LsR[rc]);}
void push_down2(ll x){
    if(tag2[x]==-INF) return;
    LsR[lc]=max(LsR[lc],tag2[x]),tag2[lc]=max(tag2[lc],tag2[x]);
    LsR[rc]=max(LsR[rc],tag2[x]),tag2[rc]=max(tag2[rc],tag2[x]);
    tag2[x]=-INF;
}
void build2(ll x,ll l,ll r){
    tag2[x]=-INF;
    if(l==r){LsR[x]=l;return;}
    build2(lc,l,mid),build2(rc,mid+1,r),push_up2(x); 
} 
void chg2(ll x,ll l,ll r,ll L,ll R,ll v){
    if(L<=l&&r<=R){
        LsR[x]=max(LsR[x],v),tag2[x]=max(tag2[x],v);
        return;
    }
    push_down2(x);
    if(L<=mid) chg2(lc,l,mid,L,R,v);
    if(R>mid) chg2(rc,mid+1,r,L,R,v);
    push_up2(x);
}
ll query2(ll x,ll l,ll r,ll p){
    if(l==r) return LsR[x];
    push_down2(x);
    if(p<=mid) return query2(lc,l,mid,p);
    return query2(rc,mid+1,r,p);
}
void solve(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++) cin>>pls[i];
    build1(1,1,n);build2(1,1,n);pls[0]=-INF;
    while(m--){
        ll opt,x,y;cin>>opt>>x>>y;
        if(opt==1){
            chg1(1,1,n,x,y,x-1);
            chg2(1,1,n,x,y,y+1);
        }
        else{
            ll L1=query1(1,1,n,y),R2=query2(1,1,n,x);
            ll ans=INF;
            if(L1!=0) ans=min(ans,pls[y]-pls[min(L1,x)]);
            if(R2!=n+1) ans=min(ans,pls[max(R2,y)]-pls[x]);
            if(R2>y) ans=min(ans,getmin1(1,1,n,y,R2-1));
            if(ans==INF) cout<<"-1\n";
            else cout<<ans<<"\n";
        }
    }
} 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll T;cin>>T;while(T--) solve();
    return 0;
}