【线段树】2021牛客暑期多校训练营1 J Journey among Railway Stations
2021-08-27 13:21:00 # ACM

题链

题目解析

给定每个车站的停车时间区间以及相邻车站之间的路程花费时间，包含三个操作：
  $1.$ $0$ $L$ $R$ 表示车从 $L$ 出发能否在 $[L,R]$ 所有车站都停留；
  $2.$ $1$ $i$ $w$ 表示将第 $i$ 段路的时间花费改为 $w$；
  $3.$ $2$ $i$ $p$ $q$ 表示将第 $i$ 个车站的停车时间区间改为 $[p,q]$；

线段树维护区间问题；

定义车站区间： $L$ 到 $R$ 的车站集合；
定义节点信息：{
  最早出发时间 $op$ ；
  最晚到达时间 $ed$ ；
  该车站区间前一段路的花费 $precost$ ；
  该车站区间总路程花费 $sumcost$ ；
  该车站区间 $L$ 到 $R$ 是否可达 $ok$ ；
}

对于两个节点的合并：
  有相邻两车站区间 $t1,t2$，$t2$ 在 $t1$ 之后，设合并结果为 $t$，因为 $t1$ 到 $t2$ 有一段中间路程 $cost$，也就是 $t2$ 的 $precost$，则设 $t2’$ 为 $t2$ 的 $op,ed$ 都减去 ( $t2.precost + t1.sumcost$ )，那么：
   $t.op = max(t1.op,t2’.op)$;
   $t.ed = min(t1.ed,t2’.ed)$;
   $t.precost = t1.precost$;
   $t.sumcost = t1.sumcost + t2’.sumcost + t2’.precost$;
   $t.ok = t1.ok$ && $t2.ok$ && $(t1.op <= t2.op)$;

两个修改就直接修改节点对应信息，查询就合并后查 $ok$ 的值；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define eps 1e-3
#define MAXN 1e9
#define MS 1000009
#define mod 1000000007
#define B1 131
#define B2 13331

LL n,m,k;
struct node{
	LL op,ed;
	LL precost;
	LL sumcost;
	LL ok;
}p[MS<<2];
LL u[MS],v[MS];
LL cost[MS];

node cross(node t1,node t2){
	node t;
	t.op = max( t1.op ,t2.op );
	t.ed = min( t1.ed ,t2.ed );
	t.precost = t1.precost;
	t.sumcost = t1.sumcost + t2.sumcost + t2.precost;
	t.ok = ( t1.op <= t2.ed && t1.ok && t2.ok)? 1 : 0;
	return t;
}

void push_up(int rt){
	node t1 = p[ls];
	node t2 = p[rs];
	t2.op -= ( t2.precost + t1.sumcost );
	t2.ed -= ( t2.precost + t1.sumcost );
	p[rt] = cross(t1,t2);
}

void build(int l,int r,int rt){
	if(l == r){
		p[rt] = {u[l],v[l],cost[l],0,1};
		return;
	}
	int m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
	push_up(rt);
}

void update(int pos,int l,int r,int rt){
	if(l == r){
		p[rt] = {u[l],v[l],cost[l],0,1};
		return;
	}
	int m = l+r>>1;
	if(m >= pos) update(pos,l,m,ls);
	else update(pos,m+1,r,rs);
	push_up(rt);
}

node get_ans(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return p[rt];
	}
	int m = l+r>>1;
	if(m < L) return get_ans(L,R,m+1,r,rs);
	else if(m >= R) return get_ans(L,R,l,m,ls);
	else{
		node t1 = get_ans(L,R,l,m,ls);
		node t2 = get_ans(L,R,m+1,r,rs);
		t2.op -= ( t2.precost + t1.sumcost );
		t2.ed -= ( t2.precost + t1.sumcost );
		return cross(t1,t2);
	}
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> u[i];
	for(int i=1;i<=n;i++) cin >> v[i];
	for(int i=2;i<=n;i++) cin >> cost[i];
	build(1,n,1);
	cin >> m;
	while(m--){
		LL op,x,y,z;
		cin >> op;
		if(op == 0){
			cin >> x >> y;
			node ans = get_ans(x,y,1,n,1);
			if(ans.ok) cout << "Yes\n";
			else cout << "No\n";
		}
		else if(op == 1){
			cin >> x;
			cin >> cost[x+1];
			update(x+1,1,n,1);
		}
		else if(op == 2){
			cin >> z;
			cin >> u[z] >> v[z];
			update(z,1,n,1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	int ce;
	cin >> ce;
	while(ce--){
		solve();
	}
	
	
	
	return 0;
}

Prev
2021-08-27 13:21:00 # ACM
Next