Journey among Railway Stations

题目描述

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

范围

\(N,Q \leq 1000000\)

题解

维护四个变量\(st,ed,c,ok\)，表示当前点到下一个点的最早时间、到当前点的最晚时间，当前点的通过代价，当前点能否通过。

线段树维护区间是否可行。

代码

#include 
using namespace std;
#define ls now << 1
#define rs now << 1 | 1
const int N = 1e6 + 10;

struct node {
	int ok;
	int c;
	int u;
	int v;
}t[N * 4];

int c[N];
int u[N];
int v[N];

int read () {
	int q = 0,f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-')f = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		q = q * 10 + ch - '0';
		ch = getchar();
	}
	return q * f;
}

node merge(node a,node b) {
	node c;
	c.ok = a.ok & b.ok;
	if(a.u > b.v) {
		c.ok = 0;
	}
	c.c = a.c + b.c;
	c.u = max(a.u + b.c,b.u);
	c.v = min(a.v,b.v - a.c);
	return c;
}

void up (int now) {
	t[now] = merge(t[ls],t[rs]);
}
void build(int l,int r,int now) {
	if(l == r) {
		t[now].ok = 1;
		t[now].c = c[l];
		t[now].u = u[l] + c[l];
		t[now].v = v[l];
		return;
	}
	int mid = l + r >> 1;
	build(l,mid,ls);
	build(mid + 1,r,rs);
	up(now);
}

void modify(int l,int r,int now,int k) {
	if(l == r) {
		t[now].ok = 1;
		t[now].c = c[l];
		t[now].u = u[l] + c[l];
		t[now].v = v[l];
		return;
	}
	int mid = l + r >> 1;
	if(k <= mid) {
		modify(l,mid,ls,k);
	}
	else {
		modify(mid + 1,r,rs,k);
	}
	up(now);
}


node query(int l,int r,int now,int ql,int qr) {
	if(l == ql and r == qr) {
		return t[now];
	}
	int mid = l + r >> 1;
	if(qr <= mid) {
		return query(l,mid,ls,ql,qr);
	}else if (ql > mid) {
		return query(mid + 1,r,rs,ql,qr);
	}
	else {
		return merge(query(l,mid,ls,ql,mid),query(mid + 1,r,now << 1 | 1,mid + 1,qr));
	}
}


int T;
int n;

int main () {
	cin >> T;
	while(T --) {
		n = read();
		for(int i = 1;i <= n; ++i) u[i] = read();
		for(int i = 1;i <= n; ++i) v[i] = read();
		for(int i = 1;i < n ; ++i) c[i] = read();
		build(1,n,1);
		int q = read();
		while(q --) {
			int op = read();
			if(op == 0) {
				int l = read(),r = read();
				int ok = query(1,n,1,l,r).ok;
				if(ok) puts("Yes");
				else puts("No");
			}
			else if(op == 1) {
				int k = read(),w = read();
				c[k] = w;
				modify(1,n,1,k);
			}
			else {
				int k = read(),p = read(),q = read();
				u[k] = p;
				v[k] = q;
				modify(1,n,1,k);
			}
		}
	}
	return 0;
}