专栏文章

题解：P14255 列车（train）

HHisy
P14255题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mink9zht
此快照首次捕获于
2025/12/02 03:47
3 个月前
此快照最后确认于
2025/12/02 03:47
3 个月前
查看原文

前言

比赛时调了半天的代码，赛后发现男孩只是少判了边界就被活活 Hack 掉了 100pts。

分析

根据题意可以发现，整个火车系统可以理解为 n2n^2 个点，每一次操作为：
  • 把 x∈[l,r],y∈[l,r]x\in[l,r],y\in[l,r] 的点之间道路全部删除。
  • 查询从 xx 到 yy 的最短路。
容易想到一个性质，即为只需要找到一趟列车即可。若有转乘点 d1,d2⋯dkd_1,d_2\cdots d_k，则有 P=pr−pk+pk−pk−1⋯−p1+p1−pl=pr−plP=p_r-p_k+p_k-p_{k-1}\cdots-p_1+p_1-p_l=p_r-p_l，在一趟列车可以到达的情况下所有方案均是等价的。
所以我们的操作变为了：初始时有 n×(n−1)2\frac{n\times(n-1)}{2} 个区间，[l,r](1≤l<r≤n)[l,r](1\le l<r\le n)：
  • 删除 [l,r]([l,r]∈[x,y])[l,r]([l,r]\in[x,y])。
  • 查询最小（价值）的 [l,r][l,r] 使 [l,r][l,r] 没被删除且 [x,y]∈[l,r][x,y]\in[l,r]。
这个该怎么维护呢？可以考虑一种类似于挂链或者并查集的方式：记 preipre_i 表示 ii 之前最后一个没有停开的点，即 preipre_i 为最后一个可以直达 ii 的点。
所以操作变为了初始时 prei=ipre_i=i，有：
  • 每次将 [x,y][x,y] 内的数值修改为上一个版本的 prex−1pre_{x-1}。
  • 查询 min⁡x≤mid<y(pr−ppremid)\min_{x\le mid<y}(p_r-p_{pre_{mid}})。
第二个查询操作里面有 ppremidp_{pre_{mid}}，看上去较难维护，但是发现 prepre 总是连续一段（或者单个出现），因为每一次删除 preipre_i 只能够比之前变得更前。
但是这还不足以维护，但是 prepre 其实还有单调性：
  • 初始时，prei=i>prei−1pre_i=i>pre_{i-1}。
  • 修改时，prei=prel−1≤prei+1pre_i=pre_{l-1}\le pre_{i+1}。
所以对于这个可以直接查找最后一个 prei≤rpre_i\le r 的点转移。

代码

CPP
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
typedef long long ll;
const ll INF=1e15;
int n,m;
ll p[MAXN];
struct SegementTree{
	struct node{
		ll val;
		int low,tag;
	}tree[MAXN<<2];
	inline void push_up(int root){
		tree[root].val=min(tree[root<<1].val,tree[root<<1|1].val);
		tree[root].low=min(tree[root<<1].low,tree[root<<1|1].low); 
	}
	inline int push_down(int root,int l,int r){
		int mid=(l+r)>>1;
		if(tree[root].tag==-1){
			return mid;
		}
		tree[root<<1].tag=tree[root<<1].low=tree[root].tag;
		tree[root<<1].val=p[tree[root].tag]-p[mid];
		tree[root<<1|1].tag=tree[root<<1|1].low=tree[root].tag;
		tree[root<<1|1].val=p[tree[root].tag]-p[r];
		tree[root].tag=-1;
		return mid;
	}
	inline void build(int root,int l,int r){
		tree[root].tag=-1;
		if(l==r){
			tree[root].low=l+1;
			tree[root].val=p[l+1]-p[l];
			return;
		} 
		int mid=(l+r)>>1;
		build(root<<1,l,mid);
		build(root<<1|1,mid+1,r);
		push_up(root);
	}
	inline void change(int root,int l,int r,int L,int R,int val){
		if(L<=l&&r<=R){
			tree[root].tag=tree[root].low=val;
			tree[root].val=p[val]-p[r];
			return;
		}
		int mid=push_down(root,l,r);
		if(L<=mid){
			change(root<<1,l,mid,L,R,val);
		}
		if(mid<R){
			change(root<<1|1,mid+1,r,L,R,val);
		}
		push_up(root);
	}
	inline int find(int root,int l,int r,int val){
		if(l==r){
			return l*(tree[root].low<=val);
		}
		int mid=push_down(root,l,r);
		if(tree[root<<1|1].low<=val){
			return find(root<<1|1,mid+1,r,val);
		}
		return find(root<<1,l,mid,val);
	}
	inline ll query(int root,int l,int r,int L,int R){
		if(L<=l&&r<=R){
			return tree[root].val;
		}
		int mid=push_down(root,l,r);
		if(L>mid){
			return query(root<<1|1,mid+1,r,L,R);
		}
		if(mid>=R){
			return query(root<<1,l,mid,L,R);
		}
		return min(query(root<<1,l,mid,L,R),query(root<<1|1,mid+1,r,L,R));
	}
	inline void print(int root,int l,int r){
		if(l==r){
			printf("{%d %lld} ",tree[root].low,tree[root].val);
			return;
		}
		int mid=push_down(root,l,r);
		print(root<<1,l,mid);
		print(root<<1|1,mid+1,r);
	}
}Tree;
inline void solve(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&p[i]);
	}
	p[0]=-INF;
	p[n+1]=INF;
	Tree.build(1,1,n);
	while(m--){
//		Tree.print(1,1,n);
//		putchar('\n');
		int opt,x,y;
		scanf("%d %d %d",&opt,&x,&y);
		if(opt==1){
			int pos=min(y,Tree.find(1,1,n,y+1));
//			cout<<pos<<endl;
			if(pos>=x){
				Tree.change(1,1,n,x,min(pos,y),y+1);
//				cout<<x<<" "<<min(pos,y)<<" "<<y+1<<endl;
			}
		}else{
			int pos=min(x,Tree.find(1,1,n,y));
//			cout<<y<<":"<<pos<<endl;
			ll ans=INF;
			if(pos>=1){
				ans=min(ans,p[y]-p[pos]);
			}
			if(pos<x){
				ans=min(ans,Tree.query(1,1,n,pos+1,x));
			}
			if(ans>p[n]-p[1]){
				ans=-1;
			}
			printf("%lld\n",ans);
		}
	}
}
signed main(){
	int T;
	scanf("%d",&T);
	while(T--){
		solve();
	}
	return 0;
}

评论

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

正在加载评论...