专栏文章

P14255 列车（train）题解

LLyz09G410/G407
P14255题解参与者 9已保存评论 10

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@minkmadn
此快照首次捕获于
2025/12/02 03:57
3 个月前
此快照最后确认于
2025/12/02 03:57
3 个月前
查看原文
出题人题解。

解法 1

暴力维护每趟列车的状态，查询暴力枚举每趟列车。
时间复杂度 O(Tmn2)O(Tmn^2)，期望通过测试点 1∼31\sim 3。

解法 2

下文以列车 [l,r][l,r] 表示以 ll 为起点站、rr 为终点站的列车。
若列车 [l,r][l,r] 被停开，则列车 [l+1,r][l+1,r] 和列车 [l,r−1][l,r-1] 一定被停开。
若列车 [l,r][l,r] 没有被停开，则列车 [l−1,r][l-1,r] 和列车 [l,r+1][l,r+1] 一定没有被停开。
也就是说如果固定起点站/终点站，列车是否被停开关于它的终点站/起点站具有单调性。所以我们可以对于每个 ii 维护 fif_i 表示列车 [k1,i][k_1,i] （k1>fik_1> f_i）均已被停开，列车 [k2,i][k_2,i]（k2≤fik_2\leq f_i）均未被停开。
停开事件相当于对于 xi≤k≤yix_i\leq k\leq y_i 的 kk 进行 fk←min⁡(fk,xi−1)f_k\leftarrow \min(f_k,x_i-1)。查询事件则遍历每个右端点，查询搭乘列车 [min⁡(xi,fj),max⁡(yi,j)][\min(x_i,f_j),\max(y_i,j)] 的代价的最小值。
时间复杂度 O(Tmn)O(Tmn)，期望通过测试点 1∼71\sim 7。

解法 3

对于每次停开事件令 fyi←min⁡(fyi,xi−1)f_{y_i}\leftarrow \min(f_{y_i},x_i-1)，所有停开事件完成之后依次从 n−1∼1n-1\sim 1 遍历 ii，且令 fi←min⁡(fi,fi+1)f_{i}\leftarrow \min(f_i,f_{i+1})，这样就省去了解法 2 中停开事件的遍历修改。
对于查询事件，考虑列车 [fj,j][f_j,j] 对于 xi,yix_i,y_i 的贡献，可以分为三类：
  1. fj≤xif_j\leq x_i 且 yi>jy_i>j。
  2. fj>xif_j>x_i 且 yi≤jy_i\leq j。
  3. fj≤xif_j\leq x_i 且 yi≤jy_i\leq j。
因为当 ii 增大时，fif_i 单调不降（维护的最后一步为 fi←min⁡(fi,fi+1)f_{i}\leftarrow \min(f_i,f_{i+1})），所以以上三类列车 [fi,i][f_i,i] 的 ii 在值域上三个不交的区间，可以使用二分等状物找到区间的界限，并用 ST 表区间查询。
时间复杂度 O(T(n+m)log⁡n)O(T(n+m)\log n)，期望通过测试点 8∼108\sim 10。

解法 4

考虑查询时不枚举 fi=fi+1f_i=f_{i+1} 的 ii，令大于 i0i_0 最小的被枚举到的 ii 为 i1i_1，则一定有 fi1≥i0−1f_{i_1}\geq i_0-1。
对于贡献为第 1 类或第 3 类的列车 [fi,i][f_i,i]，显然只有 fif_i 最大/ ii 最小的列车 [fi,i][f_i,i] 才能去到该类列车的最小代价。对于第 2 类列车只有 O(1)O(1) 个，因此对于单次查询事件总的有用的列车个数是 O(1)O(1) 级别的，直接枚举即可。
时间复杂度 O(T(n+m)log⁡n)O(T(n+m)\log n)，期望通过测试点 11,1211,12。

解法 5

因为后面的停开事件的列车范围是包含前面的停开事件的，因此查询事件只需要考虑在此之前最后一次停开事件即可。
时间复杂度 O(T(n+m))O(T(n+m))，期望通过测试点 13,1413,14。

解法 6

考虑去掉列车范围被包含的停开事件，可以使用珂朵莉树在线维护范围互不包含的列车 [fi,i][f_i,i]。
第 1 类列车和第 3 类列车可以根据解法 4 中的结论快速找到对应的唯一的列车，第 2 类列车可以暴力枚举贡献。
当 xi,yix_i,y_i 随机时一次查询事件的 xi,yix_i,y_i 期望并不会被很多列车 [fi,i][f_i,i] 所包含，可以直接遍历。
时间复杂度 O(T(n+mc)log⁡n)O(T(n+mc)\log n)，其中 cc 是一次查询事件的 xi,yix_i,y_i 被列车 [fi,i][f_i,i] 包含的列车个数，期望通过测试点 1∼71\sim 7 以及 11∼1811\sim 18。

解法 7

考虑使用线段树维护 fif_i，因为对于任意时刻有 fi≤fi+1f_i\leq f_{i+1}，所以每次可以在线段树上暴力取 min（若当前区间 fif_i 最大值小于等于取 min 的值则直接退出，若当前区间 fif_i 最小值大于等于取 min 的值则区间赋值），维护每个 ii 的 pi−pfip_{i}-p_{f_i}，以及区间 pi−pfip_{i}-p_{f_i} 的 min。
可以通过线段树上二分找出解法 3 中三类列车的分界点，在线段树上分别查询区间 pi−pfip_i-p_{f_i} 的 min 以及单点 fif_i 的值即可。
时间复杂度 O(T(n+m)log⁡n)O(T(n+m)\log n)，期望通过测试点 1∼251\sim 25。
这个题还有别的做法，例如 ODT+线段树、分块等，不过这些都是我一开始没有预料到的。
对于本题被卡常数的选手我感到抱歉，一个方面是 cz 说下发文件不能太大，因此 nn 大的数据 TT 没有给满导致部分选手以为自己跑得很快，另一方面是有验题人写了个平方解法冲过了所有点，为了卡这个做法写了半天 Gen 也只卡到了 2.0s 左右，再加上 std 跑了 550ms，验题人中最慢的也只跑了 1.1s，因此开了 1.5s。但是如果平方过题就成追忆了。
有人没发现 fif_i 有单调性以为必须要吉司机才能做，我不说是谁（
我的代码CPP
#include<iostream>
using namespace std;
#define N 100010
int t,n,m,p[N];
class sgtree
{
	public:
		#define sN 400010
		int mi[sN],ma[sN],val[sN],tag[sN];
		void build(int o,int l,int r)
		{
			tag[o]=1000000000;
			if(l==r)
			{
				mi[o]=ma[o]=p[l];
				val[o]=0;
				return;
			}
			int mid=l+r>>1;
			build(o<<1,l,mid);
			build(o<<1|1,mid+1,r);
			mi[o]=min(mi[o<<1],mi[o<<1|1]);
			ma[o]=max(ma[o<<1],ma[o<<1|1]);
			val[o]=min(val[o<<1],val[o<<1|1]);
		}
		void pushdown(int o,int l,int r)
		{
			if(tag[o]>=1000000000)
			 return;
			int mid=l+r>>1;
			tag[o<<1]=tag[o];
			mi[o<<1]=ma[o<<1]=tag[o];
			val[o<<1]=p[l]-tag[o];
			tag[o<<1|1]=tag[o];
			mi[o<<1|1]=ma[o<<1|1]=tag[o];
			val[o<<1|1]=p[mid+1]-tag[o];
			tag[o]=1000000000;
		}
		void update(int o,int l,int r,int x,int y,int k)
		{
			if(l>y||r<x)
			 return;
			if(k>=ma[o])
			 return;
			if(l>=x&&r<=y&&k<=mi[o])
			{
				tag[o]=k;
				mi[o]=ma[o]=k;
				val[o]=p[l]-k;
				return;
			}
			pushdown(o,l,r);
			int mid=l+r>>1;
			update(o<<1,l,mid,x,y,k);
			update(o<<1|1,mid+1,r,x,y,k);
			mi[o]=min(mi[o<<1],mi[o<<1|1]);
			ma[o]=max(ma[o<<1],ma[o<<1|1]);
			val[o]=min(val[o<<1],val[o<<1|1]);
		}
		int querybound(int k,int n)
		{
			if(ma[1]<=k)
			 return n;
			int o=1,l=1,r=n,ans=0;
			while(l<r)
			{
				pushdown(o,l,r);
				int mid=l+r>>1;
				if(ma[o<<1]<=k)
				{
					l=mid+1;
					o=(o<<1|1);
				}
				else
				{
					r=mid;
					o=(o<<1);
				}
			}
			return l-1;
		}
		int queryone(int o,int l,int r,int x)
		{
			if(l==r)
			 return mi[o];
			pushdown(o,l,r);
			int mid=l+r>>1;
			if(x<=mid)
			 return queryone(o<<1,l,mid,x);
			else
			 return queryone(o<<1|1,mid+1,r,x);
		}
		int querymival(int o,int l,int r,int x,int y)
		{
			if(l>y||r<x)
			 return 1000000000;
			if(l>=x&&r<=y)
			 return val[o];
			pushdown(o,l,r);
			int mid=l+r>>1;
			int q1=querymival(o<<1,l,mid,x,y);
			int q2=querymival(o<<1|1,mid+1,r,x,y);
			return min(q1,q2);
		}
}tr;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		if(n>100000||m>100000)
		 exit(111);
		p[0]=-1000000000;
		for(int i=1;i<=n;i++) 
		{
			cin>>p[i];
			if(p[i]<=p[i-1])
			 exit(112);
		}
		tr.build(1,1,n);
		for(int i=1;i<=m;i++)
		{
			int opt,x,y;
			cin>>opt>>x>>y;
			if(opt<1||opt>2)
			 exit(113);
			if(x<1||x>y||y>n)
			 exit(114);
			if(opt==1)
			{
				tr.update(1,1,n,x,y,p[x-1]);
			}
			else
			{
				int ans=1000000000;
				int h=tr.querybound(p[x]-1,n);
				if(h<y)
				{
					cout<<p[y]-p[x]<<"\n";
					continue;
				}
				ans=min(ans,tr.querymival(1,1,n,y,h));
				if(h<n)
				 ans=min(ans,p[h+1]-p[x]);
				if(ans<=p[n]-p[1])
				 cout<<ans<<"\n";
				else
				 cout<<-1<<"\n";
			}
		}
	}
}

评论

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

正在加载评论...