Journey among Railway Stations

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 524288K，其他语言1048576K

Articles

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]$ every day. In other words, if a train arrives before time $u_i$ or after time $v_i$ , it can not stop at station $i$ .

Many trains travel through these stations every day. It takes $cost_i$ 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$ , 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 $cost_i=w$ .
Station $i$ change its open time to $[p,q]$ . i.e., set $u_i=p,v_i=q$ .

Please answer each question of the first type.

Input

The first line of the input contains an integer $T (1 \le T \le 10^4)$ , indicating the number of test cases.

For each test case:

The first line contains a integer $n(2 \le n \le 10^6)$ , indicating the number of stations. The second and third line contains $n$ intergers each, indicating the sequence $u_i$ and $v_i(1 \le u_i \le v_i \le 10^9)$ .The fourth line contains $n−1$ integers, indicating the sequence $cost_i(1 \le cost_i \le 10^9)$

The fifth line contains a integer $Q(1 \le Q \le 10^6)$ . 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 \le i < n, 1 \le w \le 10^9)$ : change $cost_i$ to a new value ${w}$ .
$2, i, p, q(1 \le i \le n, 1 \le p \le q \le 10^9)$ : 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 $10^6$ .

Ouput

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’.

Example

input

ouput

1
2
3

Yes
Yes
No

Tutorial

$a_i$ 为开始时间， $b_i$ 为截止时间， $d_i$ 为执行花费时间.

新定义如下两种变量

$pa_i=a_i + \sum_{k=i}^{n}d_i$

$pb_i=b_i+\sum_{k=i+1}^{n}d_i$

若对于任意的 $i$ 都满足 $max\{pa_1,pa_2,...,pa_i\} \leq pb_i$ ，则表示可以按顺序完成所有事件。

上述判断和修改操作均可用线段树维护。（分治，合并时判断前断最大的 $pa_i$ 是否小于等于后断最小的 $pb_i$ ）

本题中第 $i$ 个站点的开启时间相当于 $a_i$ ，第 $i+1$ 个站点的关闭时间相当于 $b_i$ ，第 $i$ 个站点到第 $i+1$ 个站点的花费时间相当于 $d_i$ 。

Code

#include<bits/stdc++.h>

using namespace std;	

const int maxn = 1e6+1;

long long a[maxn], b[maxn], d[maxn], pa[maxn], pb[maxn];

struct node{
    long long mx, mi, ck, lazy;
}e[maxn<<2];

void up(int root) {
    int l = root<<1, r = root<<1|1;
    e[root].mx = max(e[l].mx, e[r].mx);
    e[root].mi = min(e[l].mi, e[r].mi);
    e[root].ck = e[l].ck && e[r].ck && (e[l].mx <= e[r].mi);
}

void down(int root) {
    int lazy = e[root].lazy, l = root<<1, r = root<<1|1;
    if (lazy) {
        e[l].mx += lazy;
        e[l].mi += lazy;
        e[l].lazy += lazy;
        e[r].mx += lazy;
        e[r].mi += lazy;
        e[r].lazy += lazy;
        e[root].lazy = 0;
    }
}

void build(int root, int l, int r) {
    e[root].lazy = 0;
    if (l == r) {
        e[root].mx = pa[l];
        e[root].mi = pb[l];
        e[root].ck = (e[root].mx <= e[root].mi);
        return ;
    }
    int mid = l + r >> 1;
    build(root<<1, l, mid);
    build(root<<1|1, mid+1, r);
    up(root);
}

void updata(int root, int l, int r, int ul, int ur, long long val) {
    if (ul <= l && r <= ur) {
        e[root].mx += val;
        e[root].mi += val;
        e[root].lazy += val;
        return ;
    }
    down(root);
    int mid = l + r >> 1;
    if (mid >= ul) updata(root<<1, l, mid, ul, ur, val);
    if (mid < ur) updata(root<<1|1, mid+1, r, ul, ur, val);
    up(root);
}

void updata_(int root, int l, int r, int pos, long long val1, long long val2) {
    if (l == r) {
        e[root].mx += val1;
        e[root].mi += val2;
        e[root].ck = (e[root].mx <= e[root].mi);
        return ;
    }
    down(root);
    int mid = l + r >> 1;
    if (mid >= pos) updata_(root<<1, l, mid, pos, val1, val2);
    else updata_(root<<1|1, mid+1, r, pos, val1, val2);
    up(root);
}

node query(int root, int l, int r, int ul, int ur) {
    if (ul <= l && r <= ur) {
        return e[root];
    }
    down(root);
    int mid = l + r >> 1;
    node res1 = {LLONG_MIN, LLONG_MAX, true, 0}, res2 = {LLONG_MIN, LLONG_MAX, true, 0};
    if (mid >= ul) res1 = query(root<<1, l, mid, ul, ur);
    if (mid < ur) res2 = query(root<<1|1, mid+1, r, ul, ur);
    return {max(res1.mx, res2.mx), min(res1.mi, res2.mi), res1.ck && res2.ck && (res1.mx <= res2.mi), 0};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T --) {
        int n;
        cin >> n;
        for(int i = 1; i <= n; ++ i) {
            cin >> a[i];
        }
        for(int i = 1; i <= n; ++ i) {
            cin >> b[i];
        }
        for(int i = 1; i < n; ++ i) {
            cin >> d[i];
        }
        d[n] = 0;
        long long pre = 0;
        for(int i = n; i >= 1; -- i) {
            pre += d[i];
            if (i < n) pa[i] = a[i] + pre;
            if (i > 1) pb[i-1] = b[i] + pre;
        }
        build(1, 1, n-1);
        int q;
        cin >> q;
        while(q --) {
            int op;
            cin >> op;
            if (op == 0) {
                int l, r;
                cin >> l >> r;
                if (l == r || query(1, 1, n-1, l, r-1).ck) cout << "Yes\n";
                else cout << "No\n";
            }
            else if (op == 1) {
                long long id, val;
                cin >> id >> val;
                updata(1, 1, n-1, 1, id, -d[id]+val);
                updata_(1, 1, n-1, id, 0, d[id]-val);
                d[id] = val;
            }
            else if (op == 2) {
                long long id, aa, bb;
                cin >> id >> aa >> bb;
                if (id < n) updata_(1, 1, n-1, id, -a[id]+aa, 0);
                if (id > 1) updata_(1, 1, n-1, id-1, 0, -b[id]+bb);
                a[id] = aa;
                b[id] = bb;
            }
        }
    }
    return 0;
}