2021牛客暑期多校训练营1 J.Journey among Railway Stations

题目链接
题目描述
There are $n$ railway stations lying on a straight line, numbered from $1$ to $n$. A strange thing is, each railway station only opens for a continuous period of time [ u i , v i ] [u_i, v_i] [ui​,vi​] every day. In other words, if a train arrives before time u i u_i ui​ or after time v i v_i vi​ , it can not stop at station $i$.

Many trains travel through these stations every day. It takes c o s t i cost_i costi​ times for each train to travel from station $i$ to station $i+1$ with the top speed.

If a train driver wants to stop at station $i$ where the train may arrive early, he can choose to run slowly to meet the time requirements of that station. However, there is no way out if the train arrives late even with the top speed.

A new day is coming. As a train driver, now your train is at station $i$, plan to leave for station $j$ at time u i u_i ui​ , and stop at all stations of $i\sim j$ along the railway line. You are wondering whether your train can meet the arrival time requirements of all railway stations from $i$ to $j$ (boarding and alighting time at each station are ignored).

$Q$ days are coming, one of the following three events will happen every day.
Ask whether you can stop the train among each station $[l,r]$.
The railway line between station $i$ and station $i+1$ has been repaired and the passing time is changed to $w$. i.e., set c o s t i = w cost_i=w costi​=w.
Station $i$ change its open time to $[p,q]$. i.e., set u i = p u_i=p ui​=p, v i = q v_i=q vi​=q.
Please answer each question of the first type.
输入描述:
The first line of the input contains an integer T ( 1 ≤ T ≤ 1 0 4 ) T (1 \le T \le 10^4) T(1≤T≤104), indicating the number of test cases.

For each test case:

The first line contains a integer n ( 2 ≤ n ≤ 1 0 6 ) n(2 \le n \le 10^6) n(2≤n≤106), indicating the number of stations. The second and third line contains $n$ intergers each, indicating the sequence u i u_i ui​ and v i v_i vi​ ( 1 ≤ u i ≤ v i ≤ 1 0 9 ) (1 \le u_i \le v_i \le 10^9) (1≤ui​≤vi​≤109). The fourth line contains $n-1$ integers, indicating the sequence c o s t i ( 1 ≤ c o s t i ≤ 1 0 9 ) cost_i(1 \le cost_i \le 10^9) costi​(1≤costi​≤109).

The fifth line contains a integer Q ( 1 ≤ Q ≤ 1 0 6 ) Q(1 \le Q \le 10^6) Q(1≤Q≤106). The next $Q$ lines describe the event every day.
$0,l,r(1\le l\le r\le n)$: ask whether you can stop the train among each station $[l,r]$.
1 , i , w ( 1 ≤ i < n , 1 ≤ w ≤ 1 0 9 ) 1, i, w(1 \le i < n, 1 \le w \le 10^9) 1,i,w(1≤i<n,1≤w≤109): change c o s t i cost_i costi​ to a new value $w$.
2 , i , p , q ( 1 ≤ i ≤ n , 1 ≤ p ≤ q ≤ 1 0 9 ) 2, i, p, q(1 \le i \le n, 1 \le p \le q \le 10^9) 2,i,p,q(1≤i≤n,1≤p≤q≤109): the open time of station $i$ is changed to $[p,q]$.

It’s guaranteed that the sum of $\max (n,Q)$ over all test cases does not exceed 1 0 6 10^6 106 .
输出描述:
For each test case, output the answer for each question of the first type: Output ‘Yes’ if you can stop the train successfully, otherwise ‘No’.
示例1
输入

1
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

输出

Yes
Yes
No

对于某区间，设 $lim$ 为到达该区间的最晚时间，$nxt$ 为到达下一个区间的最早时间，$smc$ 为通过该区间路程上花费的时间。可以看出两个向邻区间可以合并，因此考虑用线段树维护。

#includeusing namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int u[N], v[N], c[N];
int T, n, Q;struct Seg_Tree {struct node {int lim, nxt, smc;inline node operator+(node a) const {if (nxt > a.lim)return {-1, -1, -1};return {max(-1, min(lim, a.lim - smc)), max(nxt + a.smc, a.nxt), smc + a.smc};}};struct {int l, r;node dat;} t[N << 2];void build(int p, int l, int r) {t[p].l = l, t[p].r = r;if (l == r) {t[p].dat = {v[l], u[l] + c[l], c[l]};return;}int mid = (l + r) >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);t[p].dat = t[p << 1].dat + t[p << 1 | 1].dat;}void change(int p, int x) {if (t[p].l == t[p].r) {t[p].dat = {v[x], u[x] + c[x], c[x]};return;}int mid = (t[p].l + t[p].r) >> 1;change(p << 1 | (x > mid), x);t[p].dat = t[p << 1].dat + t[p << 1 | 1].dat;}node ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r)return t[p].dat;int mid = (t[p].l + t[p].r) >> 1;node res = {INF, 0, 0};if (l <= mid)res = ask(p << 1, l, r);if (r > mid)res = res + ask(p << 1 | 1, l, r);return res;}
} S;int main() {scanf("%d", &T);while (T--) {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &u[i]);for (int i = 1; i <= n; i++)scanf("%d", &v[i]);for (int i = 1; i <= n - 1; i++)scanf("%d", &c[i]);scanf("%d", &Q);S.build(1, 1, n);while (Q--) {int o;scanf("%d", &o);if (o == 0) {int l, r;scanf("%d%d", &l, &r);puts(S.ask(1, l, r).lim == -1 ? "No" : "Yes");} else if (o == 1) {int i, w;scanf("%d%d", &i, &w);c[i] = w, S.change(1, i);} else {int i, p, q;scanf("%d%d%d", &i, &p, &q);u[i] = p, v[i] = q, S.change(1, i);}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！