专栏文章

题解：P14255 列车（train）

ggesong1234
P14255题解参与者 29已保存评论 29

文章操作

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

当前评论
29 条
当前快照
1 份
快照标识符
@minklmup
此快照首次捕获于
2025/12/02 03:56
3 个月前
此快照最后确认于
2025/12/02 03:56
3 个月前
查看原文
题目传送门：P14255 列车。

思路

开往 OI 未来的列车能不能在这一年不要停开。
我们在这里定义修改操作为题目中的停开操作，查询操作为题目询问花费。
记 fif_i 为第 ii 个点能通过列车直接到达的点的编号最小值。
容易发现两个性质。
  1. ii 点一定可以通过列车直接到 fif_i 及以后所有点。
  2. fif_i 是一个不下降序列。
证明可以考虑反证法，这里不过多赘述。
接下来考虑如何动态维护 ff 的值。
在一个修改操作中，显然 ff 的值只会影响 ll 到 rr，在这中间的点的 ff 最优只能为 r+1r+1，那么相当于 fi←max⁡(fi,r+1)f_i\leftarrow \max(f_i,r+1)。
在查询操作中，找到 ff 在 11 到 ll 间小于等于 rr 的最大下标记为 xx，由性质二，如果从小于等于 xx 的位置开始，最优答案即为 min⁡i=1x(pr−pi)=pr−px\min_{i=1}^x (p_r-p_i)=p_r-p_x，对于大于 xx 的位置，答案即为 min⁡i=x+1l(pfi−pi)\min_{i=x+1}^l (p_{f_i}-p_i)。
由 ff 的性质二，用线段树和二分来维护这两种操作即可，没有什么细节，具体的可以查看代码。
希望大家能在 CSP-S 超长发挥，考出理想的成绩。

代码

CPP
#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++

评论

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

正在加载评论...