题意

有 $N$ ($1\le N\le 3\cdot10^5$) 座城市排成一行，$N-1$ 条道路连接了每一对相邻的城市。第 $i$ 条道路连接了城市 $i$ 和 $i+1$，经过它需要的时间为 $1$ 秒，且只会在 $[L_i,R_i]$ 的时间开放 (因为需要 $1$ 秒通过，所以必须在 $[L_i,R_i-1]$ 的时间出发)。Bitaro 可以使用技能使得时间变为 $1$ 秒前，也可以等待时间自然流逝。接下来有以下两种操作共 $Q$ ($1\le Q\le 3\cdot10^5$) 次：

• 将道路 $P_i$ 的开放时间改为 $[S_i,T_i]$。
• 询问 $B_i$ 时刻从城市 $A_i$ 出发，在 $D_i$ 时刻到达城市 $C_i$，最少使用技能的次数。

题解

把 $y$ 时刻在城市 $x$ 的状态看作二维平面上的点 $(x,y)$。不妨设 $A_i< C_i$，则将 $(x,y)$ 变换为 $(x,y-x)$，则问题就转化为了只能向上下右三个方向走 (向左走显然不优)，需要的最少的上下走的次数。考虑一个区间的所有 $[L_i,R_i]$ 的限制，如果它们有交，则这个区间等价于它们的交；否则，一定等价于一条路径，即只能从固定的纵坐标进入和离开，并付出一定的代价。用线段树维护每个区间的等价限制即可。

时间复杂度：$O(N+Q\log N)$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
struct Node {
    int l;
    int r;
    long long cost;
    Node(int l = -0x3fffffff, int r = 0x3fffffff, long long cost = -1) : l(l), r(r), cost(cost) {}
    friend Node operator+(const Node &lhs, const Node &rhs) {
        if (lhs.cost == -1 && rhs.cost == -1) {
            if (lhs.l > rhs.r) {
                return Node(lhs.l, rhs.r, lhs.l - rhs.r);
            } else if (lhs.r < rhs.l) {
                return Node(lhs.r, rhs.l, 0);
            } else {
                return Node(std::max(lhs.l, rhs.l), std::min(lhs.r, rhs.r));
            }
        } else if (lhs.cost == -1) {
            if (rhs.l < lhs.l) {
                return Node(lhs.l, rhs.r, rhs.cost + lhs.l - rhs.l);
            } else if (rhs.l > lhs.r) {
                return Node(lhs.r, rhs.r, rhs.cost);
            } else {
                return rhs;
            }
        } else if (rhs.cost == -1) {
            if (lhs.r < rhs.l) {
                return Node(lhs.l, rhs.l, lhs.cost);
            } else if (lhs.r > rhs.r) {
                return Node(lhs.l, rhs.r, lhs.cost + lhs.r - rhs.r);
            } else {
                return lhs;
            }
        } else {
            return Node(lhs.l, rhs.r, lhs.cost + rhs.cost + std::max(lhs.r - rhs.l, 0));
        }
    }
};
struct SegmentTree {
    const int n;
    std::vector<Node> a;
    SegmentTree(int n) : n(n), a(4 * n) {}
    void modify(int p, int l, int r, int pos, int x, int y) {
        if (r - l == 1) {
            a[p] = Node(x, y);
        } else {
            int m = (l + r) / 2;
            if (pos < m) {
                modify(2 * p, l, m, pos, x, y);
            } else {
                modify(2 * p + 1, m, r, pos, x, y);
            }
            a[p] = a[2 * p] + a[2 * p + 1];
        }
    }
    Node rangeSum(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Node();
        } else if (l >= x && r <= y) {
            return a[p];
        } else {
            int m = (l + r) / 2;
            return rangeSum(2 * p, l, m, x, y) + rangeSum(2 * p + 1, m, r, x, y);
        }
    }
    void modify(int p, int x, int y) { modify(1, 0, n, p, x, y); }
    Node rangeSum(int l, int r) { return rangeSum(1, 0, n, l, r); }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    SegmentTree t(n - 1), tR(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        int l, r;
        std::cin >> l >> r;
        t.modify(i, l - i, r - i - 1);
        tR.modify(n - 2 - i, l + i + 1, r + i);
    }
    while (q--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int p, l, r;
            std::cin >> p >> l >> r;
            --p;
            t.modify(p, l - p, r - p - 1);
            tR.modify(n - 2 - p, l + p + 1, r + p);
        } else {
            int a, b, c, d;
            std::cin >> a >> b >> c >> d;
            --a;
            --c;
            if (a < c) {
                std::cout << std::max(0ll, (Node(b - a, b - a) + t.rangeSum(a, c) + Node(d - c, d - c)).cost)
                          << "\n";
            } else {
                std::cout
                    << std::max(
                           0ll,
                           (Node(a + b, a + b) + tR.rangeSum(n - 1 - a, n - 1 - c) + Node(c + d, c + d)).cost)
                    << "\n";
            }
        }
    }
    return 0;
}