题意

有 $N$ ($2\le N\le 2\cdot10^5$) 个天线排成一行，相邻两个天线的距离为 $1$，第 $i$ 个天线的高度为 $H_i$。第 $i$ 个天线只能向与它的距离在区间 $[A_i,B_i]$ 中的天线发送消息。如果两个天线 $i$, $j$ 可以互相发消息，则定义它们的通信成本为 $|H_i-H_j|$。接下来有 $Q$ ($1\le Q\le 2\cdot10^5$) 个询问，第 $i$ 个询问为区间 $[L_i,R_i]$ 中可以互相发消息的天线对的最大通信成本 (如果不存在则为 $-1$)。

题解

不妨将询问改为求最大的 $H_i-H_j$ ($i < j$)，则重复两遍该过程即可得到答案。维护两个数组 $P_i$, $Q_i$，初始时都为 $-\infty$。从左到右枚举右端点，在 $i+A_i$ 处将 $P_i$ 修改为 $H_i$，在 $i+B_i+1$ 处将 $P_i$ 修改为 $-\infty$。假设枚举到的右端点为 $j$，则对所有的 $j-B_j\le i\le j-A_j$，$Q_i\gets \max\{Q_i,P_i-H_j\}$。当枚举到 $R_i$ 时，求出 $\max\{Q_k\mid L_i\le k\le R_i \}$ 即为答案。所有操作都可以用线段树维护。

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
constexpr int INF = 1e9;
struct SegmentTree {
    const int n;
    std::vector<int> maxA, maxB, tag;
    SegmentTree(int n) : n(n), maxA(4 * n, -INF), maxB(4 * n, -INF), tag(4 * n, -INF) {}
    void pull(int p) {
        maxA[p] = std::max(maxA[2 * p], maxA[2 * p + 1]);
        maxB[p] = std::max(maxB[2 * p], maxB[2 * p + 1]);
    }
    void add(int p, int v) {
        tag[p] = std::max(tag[p], v);
        maxB[p] = std::max(maxB[p], maxA[p] + v);
    }
    void push(int p) {
        add(2 * p, tag[p]);
        add(2 * p + 1, tag[p]);
        tag[p] = -INF;
    }
    void modifyA(int p, int l, int r, int pos, int v) {
        if (r - l == 1) {
            maxA[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (pos < m) {
            modifyA(2 * p, l, m, pos, v);
        } else {
            modifyA(2 * p + 1, m, r, pos, v);
        }
        pull(p);
    }
    void rangeModify(int p, int l, int r, int x, int y, int v) {
        if (l >= y || r <= x)
            return;
        if (l >= x && r <= y) {
            add(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeModify(2 * p, l, m, x, y, v);
        rangeModify(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    int rangeMaxB(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x)
            return -INF;
        if (l >= x && r <= y)
            return maxB[p];
        int m = (l + r) / 2;
        push(p);
        return std::max(rangeMaxB(2 * p, l, m, x, y), rangeMaxB(2 * p + 1, m, r, x, y));
    }
    void modifyA(int pos, int v) { modifyA(1, 0, n, pos, v); }
    void rangeModify(int l, int r, int v) { rangeModify(1, 0, n, l, r, v); }
    int rangeMaxB(int l, int r) { return rangeMaxB(1, 0, n, l, r); }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> h(n), a(n), b(n);
    for (int i = 0; i < n; ++i) std::cin >> h[i] >> a[i] >> b[i];
    int q;
    std::cin >> q;
    std::vector<int> l(q), r(q);
    for (int i = 0; i < q; ++i) {
        std::cin >> l[i] >> r[i];
        --l[i];
    }
    std::vector<int> ans(q, -1);
    auto solve = [&]() {
        std::vector<std::vector<int>> queries(n);
        for (int i = 0; i < q; ++i) queries[r[i] - 1].push_back(i);
        std::vector<std::vector<std::pair<int, int>>> mod(n);
        for (int i = 0; i < n; ++i) {
            if (i + a[i] < n)
                mod[i + a[i]].emplace_back(i, h[i]);
            if (i + b[i] + 1 < n)
                mod[i + b[i] + 1].emplace_back(i, -INF);
        }
        SegmentTree t(n);
        for (int i = 0; i < n; ++i) {
            for (auto [pos, v] : mod[i]) t.modifyA(pos, v);
            t.rangeModify(std::max(0, i - b[i]), std::max(0, i - a[i] + 1), -h[i]);
            for (auto j : queries[i]) ans[j] = std::max(ans[j], t.rangeMaxB(l[j], r[j]));
        }
    };
    solve();
    std::reverse(h.begin(), h.end());
    std::reverse(a.begin(), a.end());
    std::reverse(b.begin(), b.end());
    for (int i = 0; i < q; ++i) {
        l[i] = n - l[i];
        r[i] = n - r[i];
        std::swap(l[i], r[i]);
    }
    solve();
    for (int i = 0; i < q; ++i) std::cout << ans[i] << "\n";
    return 0;
}