专栏文章

题解：P14255 列车（train）

zzyn0309
P14255题解参与者 4已保存评论 4

文章操作

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

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

思路

首先定义 fif_i 为第 ii 个点往前能直接到达的编号最大的点，容易发现这样第 ii 个点往前能直接到的区间就是 [1,fi][1,f_i]。

操作 11

操作 11 相当于把所有 i∈[x,y]i \in [x,y] 的 fif_i 变为 min⁡(fi,x−1)\min(f_i,x-1)。注意到初始值是 fi=if_i=i，所以每一次操作 11 都不会使得 fif_i 小于它前面的 fjf_j，因此 ff 是单调不降的。
这样就可以直接用一棵线段树维护 ff 数组了，代码如下：
CPP
inline void update(int u,int l,int r,int val){
	if(t[u].maf<=val)return;
	if(l<=t[u].l&&t[u].r<=r){
	  if(t[u].mif>=val){
		work(u,val);
		return;
	  }
	  push_down(u);
	  update(lson(u),l,r,val);
	  update(rson(u),l,r,val);
	  push_up(u);
	  return;
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(l<=mid)update(lson(u),l,r,val);
	if(r>mid)update(rson(u),l,r,val);
	push_up(u);
}
由于 ff 数组的单调性，线段树上的每一层最多只有一个完全被包含的结点向下走，因此单次操作 11 是 O(log⁡n)O(\log n) 的。

操作 22

对于一个固定的右端点，肯定是贪心选最靠后的左端点优，因此一次查询的答案为 min⁡i=ynpi−pmin⁡fi,x\min_{i=y}^n p_i - p_{\min_{f_i,x}}。
同样根据 fif_i 的单调性，可以发现 min⁡fi,x\min_{f_i,x} 取值为 fif_i 的和取值为 xx 的都是一段连续的区间，可以直接在线段树上查询，复杂度证明与修改类似，代码如下：
CPP
inline int query(int u,int l,int r){
	if(t[u].l>=r){
	  if(t[u].maf<=l)return t[u].mi2;
	  else if(t[u].mif>=l)return t[u].mi1-p[l];
	  push_down(u);
	  return min(query(lson(u),l,r),query(rson(u),l,r));
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(r<=mid)return min(query(lson(u),l,r),query(rson(u),l,r));
	else return query(rson(u),l,r);
}
时间复杂度 O(T(n+mlog⁡n))O(T(n+m \log n))。

Code

CPP
#include<bits/stdc++.h>
namespace fast_IO{
	#define IOSIZE 100000
		char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
	#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
	#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
	#define isdigit(ch) (ch>47&&ch<58)
	#define isspace(ch) (ch<33)
		template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
		template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
		template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
		inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
		inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
		inline void print(char x) { putchar(x); }
		inline void print(char *x) { while (*x) putchar(*x++); }
		inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
		inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
		inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
		inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
		inline void print(bool b) { putchar(b+48); }
		template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
		template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
		struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
		template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
		template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
	#define cout io
	#define cin io
}using namespace fast_IO;
using namespace std;
const int N=1e5+10,inf=1e9;
int n,m,p[N];
struct tree{
	int l,r,mi1,mi2,maf,mif,lazy;
	#define lson(u) (u<<1)
	#define rson(u) (u<<1|1)
}t[4*N];
inline void push_up(int u){
	t[u].mi1=min(t[lson(u)].mi1,t[rson(u)].mi1);
	t[u].mi2=min(t[lson(u)].mi2,t[rson(u)].mi2);
	t[u].maf=max(t[lson(u)].maf,t[rson(u)].maf);
	t[u].mif=min(t[lson(u)].mif,t[rson(u)].mif);
}
inline void build(int u,int l,int r){
	t[u].l=l;
	t[u].r=r;
	t[u].mi1=t[u].mi2=0;
	t[u].lazy=-1;
	if(l==r){
	  t[u].maf=t[u].mif=l;
	  t[u].mi1=p[l];
	  t[u].mi2=0;
	  return;
	}
	int mid=(l+r)>>1;
	build(lson(u),l,mid);
	build(rson(u),mid+1,r);
	push_up(u);
}
inline void work(int u,int val){
	t[u].maf=t[u].mif=t[u].lazy=val;
	t[u].mi2=t[u].mi1-p[val];
}
inline void push_down(int u){
	if(t[u].lazy==-1)return;
	work(lson(u),t[u].lazy);
	work(rson(u),t[u].lazy);
	t[u].lazy=-1;
}
inline void update(int u,int l,int r,int val){
	if(t[u].maf<=val)return;
	if(l<=t[u].l&&t[u].r<=r){
	  if(t[u].mif>=val){
		work(u,val);
		return;
	  }
	  push_down(u);
	  update(lson(u),l,r,val);
	  update(rson(u),l,r,val);
	  push_up(u);
	  return;
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(l<=mid)update(lson(u),l,r,val);
	if(r>mid)update(rson(u),l,r,val);
	push_up(u);
}
inline int query(int u,int l,int r){
	if(t[u].l>=r){
	  if(t[u].maf<=l)return t[u].mi2;
	  else if(t[u].mif>=l)return t[u].mi1-p[l];
	  push_down(u);
	  return min(query(lson(u),l,r),query(rson(u),l,r));
	}
	push_down(u);
	int mid=(t[u].l+t[u].r)>>1;
	if(r<=mid)return min(query(lson(u),l,r),query(rson(u),l,r));
	else return query(rson(u),l,r);
}
inline void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>p[i];
	p[0]=-inf;
	build(1,1,n);
	int opt,l,r;
	while(m--){
	  cin>>opt>>l>>r;
	  if(opt==1)update(1,l,r,l-1);
	  else{
		int res=query(1,l,r);
		if(res>inf)cout<<"-1\n";
		else cout<<res<<"\n";
	  }
	}
}
signed main(){
	int T=1;
	cin>>T;
	while(T--)solve();
	return 0;
}

评论

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

正在加载评论...