题解 | #Journey among Railway Stations#

J - Journey among Railway Stations

题意：
个点，每个点的合法时间是，第i个点到下一个点的需要的最短时间为，每次询问从点出发到r点是否合法，或者修改值，、值。

思路：

要从点到点，可以列出式子

在合法情况下，如果到不了，那么就直接取到，否则就取。也就是说，我要在前面找一个点，这个点到当前点需要的最小时间最大，再判断当前的合法性。

设点和点，点到点时的最小时间是，点到点的最小时间是。一路加过来显然不合理，除自身点值外，两者仅相差，也看出了两者的左端点是确定的，但是右端点会随着点的改变而改变，那么不如将所有点的右端点均设为，把所有和都加上相应的，变成和，重新带回到上式，发现变成了

这个式子就很容易用线段树来维护了。线段树里维护的最大值，的最小值，以及当前的合法性。

#include <bits/stdc++.h>

using namespace std;
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid (l + r >> 1)
inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 7;

ll u[N], v[N], c[N], pre[N];
int n;

struct Seg{
    struct node{
        bool ok;
        ll uu, vv, add;
    }t[N << 2];

    node merge(node ln, node rn) {
        node tmp = ln;
        tmp.ok &= rn.ok;
        if (ln.uu > rn.vv) tmp.ok = false;
        tmp.uu = max(tmp.uu, rn.uu);
        tmp.vv = min(tmp.vv, rn.vv);
        tmp.add = 0;
        return tmp;
    }

    void up(int id) {
        t[id] = merge(t[ls], t[rs]);
    }

    void down(int id) {
        if (t[id].add == 0) return;
        ll add = t[id].add;
        t[ls].add += add, t[ls].uu += add, t[ls].vv += add;
        t[rs].add += add, t[rs].uu += add, t[rs].vv += add;
        t[id].add = 0;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            t[id].add = 0;
            t[id].ok = true;
            t[id].uu = u[l] + pre[n] - pre[l - 1];
            t[id].vv = v[l] + pre[n] - pre[l - 1];
            return;
        }
        build(ls, l, mid);
        build(rs, mid + 1, r);
        up(id);
    }

    void modify(int id, int l, int r, int ql, int qr, int pu, int pv, ll pa) {
        if (l >= ql && r <= qr) {
            if (pu != 0) {
                t[id].uu += pu - u[l];
                t[id].vv += pv - v[l];
                u[l] = pu, v[l] = pv;
            } else {
                t[id].add += pa;
                t[id].uu += pa;
                t[id].vv += pa;
            }
            return;
        }
        down(id);
        if (ql <= mid) modify(ls, l, mid, ql, qr, pu, pv, pa);
        if (qr > mid) modify(rs, mid + 1, r, ql, qr, pu, pv, pa);
        up(id);
    }

    node query(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) return t[id];
        down(id);
        bool flag = 0;
        node tmp;
        if (ql <= mid) {
            flag = 1;
            tmp = query(ls, l, mid, ql, qr);
        }
        if (qr > mid) {
            if (!flag) tmp = query(rs, mid + 1, r, ql, qr);
            else tmp = merge(tmp, query(rs, mid + 1, r, ql, qr));
        }
        return tmp;
    }

    ll getOk(int ql, int qr) {
        node tmp = query(1, 1, n, ql, qr);
        return tmp.ok;
    }
}seg;

void solve() {
    n = rd();
    for (int i = 1; i <= n; ++i) {
        u[i] = rd();
    }
    for (int i = 1; i <= n; ++i) {
        v[i] = rd();
    }
    for (int i = 1; i < n; ++i) {
        c[i] = rd();
    }
    for (int i = 1; i <= n; ++i) {
        pre[i] = c[i] + pre[i - 1];
    }
    seg.build(1, 1, n);
    int q = rd();
    while (q--) {
        int op = rd();
        if (op == 0) {
            int ql = rd(), qr = rd();
            if (seg.getOk(ql, qr)) puts("Yes");
            else puts("No");
        } else if (op == 1) {
            int i = rd(), w = rd();
            seg.modify(1, 1, n, 1, i, 0, 0, w - c[i]);
            c[i] = w;
        } else {
            int i = rd(), pu = rd(), pv = rd();
            seg.modify(1, 1, n, i, i, pu, pv, 0);
        }
    }
}

int main() {
    int t = 1;
    t = rd();
    while (t--) solve();
    return 0;
}