牛客多校2021-1-Journey among Railway Stations

2023-11-12 22:10:22

题目大意： 一段路上有 N N N个点，每个点有一个合法时间段 [ u i , v i ] [u_i, v_i] [ui,vi]，相邻两个点有一个长度。每次问，在 u i u_i ui 的时间从 i i i 出发后，能否依次经过 i + 1 j i+1~j i+1 j 的所有点，使得到达时间满足每个点的合法区间（如果提前到可以等待，迟到了失败了）。同时还可能修改一段路的长度，或者修改一个点的合法时间段。 N , Q ≤ 1000000 N, Q \leq 1000000 N,Q≤1000000

题目分析： 考虑区间 [ l , r ] [l,r] [l,r] 的限制条件，以区间 [ 1 , 3 ] [1,3] [1,3]为例，即 u 1 ≤ v 1 , m a x ( u 1 + d 1 , u 2 ) ≤ v 2 , m a x ( m a x ( u 1 + d 1 , u 2 ) + d 2 , u 3 ) ≤ v 3 u_1\leq v_1,max(u_1+d_1,u_2) \leq v_2,max(max(u_1+d_1,u_2)+d_2,u_3)\leq v_3 u1≤v1,max(u1+d1,u2)≤v2,max(max(u1+d1,u2)+d2,u3)≤v3我们设 u i ′ = u i + d i + d i + 1 + . . . + d n − 1 , v i ′ = v i + d i + d i + 1 + . . . + d n − 1 u_i'=u_i+d_i+d_{i+1}+...+d_{n-1},v_i'=v_i+d_i+d_{i+1}+...+d_{n-1} ui′=ui+di+di+1+...+dn−1,vi′=vi+di+di+1+...+dn−1，那么区间 [ 1 , 3 ] [1,3] [1,3]的限制条件就变为了 u 1 ′ ≤ v 1 ′ , m a x ( u 1 ′ , u 2 ′ ) ≤ v 2 ′ , m a x ( u 1 ′ , u 2 ′ , u 3 ′ ) ≤ v 3 ′ u_1'\leq v_1',max(u_1',u_2')\leq v_2',max(u_1',u_2',u_3')\leq v_3' u1′≤v1′,max(u1′,u2′)≤v2′,max(u1′,u2′,u3′)≤v3′线段树维护当前区间是否可行，以及当前区间中 u u u的最大值和 v v v的最小值，在区间合并时该区间是可行区间的充分条件是他的两个子区间都是可行区间并且左区间中 u u u的最大值应当小于等于右区间中 v v v的最小值。代码如下。

题目代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define LL long long
#define mxn 1000005
struct Tree{
	LL u_maxn,v_minn,lazy;
	bool ok;
}tree[mxn<<2];
LL U[mxn],V[mxn],d[mxn],_u[mxn],_v[mxn],sum[mxn],ns[mxn];
void pushup(LL loc){
	tree[loc].u_maxn=max(tree[loc<<1|1].u_maxn,tree[loc<<1].u_maxn);
	tree[loc].v_minn=min(tree[loc<<1|1].v_minn,tree[loc<<1].v_minn);
	tree[loc].ok=tree[loc<<1].ok&tree[loc<<1|1].ok;
	tree[loc].ok&=(tree[loc<<1].u_maxn<=tree[loc<<1|1].v_minn);
}
void pushdown(LL loc,LL v){
	tree[loc<<1].u_maxn-=v;
	tree[loc<<1|1].u_maxn-=v;
	tree[loc<<1].v_minn-=v;
	tree[loc<<1|1].v_minn-=v;
	tree[loc<<1].lazy+=v;
	tree[loc<<1|1].lazy+=v;
	tree[loc].lazy=0;
}
void Build(LL loc,LL L,LL R){
	tree[loc].lazy=0;
	if(L==R){
		tree[loc].ok=(_u[L]<=_v[L]);
		tree[loc].u_maxn=_u[L];
		tree[loc].v_minn=_v[L];
		return;
	}
	LL mid=(L+R)>>1;
	Build(loc<<1,L,mid);
	Build(loc<<1|1,mid+1,R);
	pushup(loc);
}
void Update_d(LL loc,LL L,LL R,LL l,LL r,LL v){
	if(l<=L&&r>=R){
		tree[loc].u_maxn-=v;
		tree[loc].v_minn-=v;
		//tree[loc].ok&=(tree[loc].u_maxn<=tree[loc].v_minn);
		tree[loc].lazy+=v;
		return;
	}
	LL mid=(L+R)>>1;
	if(tree[loc].lazy)pushdown(loc,tree[loc].lazy);
	if(r<=mid)Update_d(loc<<1,L,mid,l,r,v);
	else if(l>mid)Update_d(loc<<1|1,mid+1,R,l,r,v);
	else Update_d(loc<<1,L,mid,l,mid,v),Update_d(loc<<1|1,mid+1,R,mid+1,r,v);
	pushup(loc);
}
void Update_uv(LL loc,LL L,LL R,LL pos,LL u,LL v){
	if(L==R){
		tree[loc].u_maxn-=u;
		tree[loc].v_minn-=v;
		tree[loc].ok&=(tree[loc].u_maxn<=tree[loc].v_minn);
		return;
	}
	LL mid=(L+R)>>1;
	if(tree[loc].lazy)pushdown(loc,tree[loc].lazy);
	if(pos<=mid)Update_uv(loc<<1,L,mid,pos,u,v);
	else Update_uv(loc<<1|1,mid+1,R,pos,u,v);
	pushup(loc);
}
Tree Query(LL loc,LL L,LL R,LL l,LL r){
	if(l<=L&&r>=R)return tree[loc];
	LL mid=(L+R)>>1;
	if(tree[loc].lazy)pushdown(loc,tree[loc].lazy);
	if(r<=mid)return Query(loc<<1,L,mid,l,r);
	else if(l>mid)return Query(loc<<1|1,mid+1,R,l,r);
	else{
		Tree ns=Query(loc<<1,L,mid,l,mid),np=Query(loc<<1|1,mid+1,R,mid+1,r);
		Tree ret=(Tree){max(ns.u_maxn,np.u_maxn),min(ns.v_minn,np.v_minn),0,0};
		ret.ok=ns.ok&np.ok;
		ret.ok&=(ns.u_maxn<=np.v_minn);
		return ret;
	}
}
void Print(LL loc,LL L,LL R){
	if(L==R){
		printf("%d %d\n",tree[loc].u_maxn,tree[loc].v_minn);
		return;
	}
	LL mid=(L+R)>>1;
	if(tree[loc].lazy)pushdown(loc,tree[loc].lazy);
	Print(loc<<1,L,mid);
	Print(loc<<1|1,mid+1,R);
}
int main()
{
	
	LL t,n,m;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		for(LL i=1;i<=n;i++)
			sum[i]=ns[i]=0; 
		for(LL i=1;i<=n;i++)
			scanf("%lld",&U[i]);
		for(LL i=1;i<=n;i++)
			scanf("%lld",&V[i]);
		for(LL i=1;i<=n-1;i++)
			scanf("%lld",&d[i]);
		for(LL i=n-1;i;i--)
			sum[i]=sum[i+1]+d[i];
		for(LL i=1;i<=n;i++){
			_u[i]=U[i]+sum[i];
			_v[i]=V[i]+sum[i];
		}
		LL maxn=0;
		for(LL i=1;i<=n;i++){
			maxn=max(_u[i],maxn);
			if(_v[i]>=maxn)ns[i]=1;
		}
		Build(1,1,n);
		scanf("%lld",&m);
		while(m--){
			//Print(1,1,n);
			printf("%d\n",Query(1,1,n,1,3).ok);
			LL opt,k,u,v;
			scanf("%lld",&opt);
			if(opt==0){
				scanf("%lld %lld",&u,&v);
				if(Query(1,1,n,u,v).ok)printf("Yes\n");
				else printf("No\n");
			}
			if(opt==1){
				scanf("%lld %lld",&k,&v);
				Update_d(1,1,n,1,k,d[k]-v);
				d[k]=v;
			}
			if(opt==2){
				scanf("%lld %lld %lld",&k,&u,&v);
				Update_uv(1,1,n,k,U[k]-u,V[k]-v);
				U[k]=u;V[k]=v;
			}
		}
	}
	return 0;
}
/*
5
1 2 3 4 5
3 4 5 6 7
1 1 1 1
5
0 1 5
1 1 3
0 1 5
2 2 2 3
0 1 5
*/

码农公寓

相关文章