专栏文章

题解：P14255 列车（train）

xxixisuper九倍体水稻
P14255题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minkglm9
此快照首次捕获于
2025/12/02 03:53
3 个月前
此快照最后确认于
2025/12/02 03:53
3 个月前
查看原文
好题，质量很高。

思路

首先是一些不成熟的想法，考虑对于一个城市 ii 来说，我们用 LiL_i 表示其左边距离其最近的一个有直达 ii 车站车次的城市编号（即满足没有操作一覆盖 [Li,i][L_i,i]），同理我们也可以定义出 RiR_i 表示其右边距离其最近的一个有直达 ii 车站车次的城市编号（即满足没有操作一覆盖 [i,Ri][i,R_i]）。
简单分析即可发现，LiL_i 与 RiR_i 都是单调不降的，而对于操作一，就相当于 [x,y][x,y] 区间中的 LiL_i 对 x−1x-1 取 min⁡\min，RiR_i 对 y+1y+1 取 max⁡\max，这一部分直接丢到线段树上维护即可。
此时对于一次询问来说，直接乘坐 [Ly,y][L_y,y] 列车和 [x,Rx][x,R_x] 列车一定会比乘坐的车站端点在 Ly,RxL_y,R_x 之外的所有车次要优，但是有可能最优车次的右端点位于 [y,Rx][y,R_x] 之间，怎么办呢？
对于一个城市 u∈[y,Rx]u\in[y,R_x]，其 LuL_u 一定是小于等于 xx 的，所以如果我要做一趟以 uu 作为右端点的车次，则我的花费最小为 pu−pLup_u-p_{L_u}。
那么我们只需要维护出 pu−pLup_u-p_{L_u} 的区间最小值即可，由于 LuL_u 单调，所以区间取 min⁡\min 操作可以通过线段树上二分变成区间赋值，而如果是区间赋值的话我们就可以维护 pu−pLup_u-p_{L_u} 的最小值了。
于是你就做完了这一题，时间复杂度 O(Tmlog⁡n)O(Tm\log n)。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...