13分 求调

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;

struct Pair {
    int x, y, cost;
    Pair(int x, int y, int cost) : x(x), y(y), cost(cost) {}
};

struct Query {
    int L, R, idx;
    Query(int L, int R, int idx) : L(L), R(R), idx(idx) {}
    bool operator<(const Query& other) const {
        return R < other.R;
    }
};

int N, Q;
int H[MAXN], A[MAXN], B[MAXN];
vector<Pair> pairs;
vector<int> ans;

// 线段树用于区间最大值查询
struct SegmentTree {
    vector<int> tree;
    int n;
    
    SegmentTree(int size) {
        n = 1;
        while (n < size) n <<= 1;
        tree.assign(2 * n, -1);
    }
    
    void update(int pos, int val) {
        pos += n;
        if (tree[pos] >= val) return;
        tree[pos] = val;
        for (pos >>= 1; pos >= 1; pos >>= 1) {
            int new_val = max(tree[2*pos], tree[2*pos+1]);
            if (tree[pos] == new_val) break;
            tree[pos] = new_val;
        }
    }
    
    int query(int l, int r) {  // [l, r]
        l += n; r += n;
        int res = -1;
        while (l <= r) {
            if (l % 2 == 1) res = max(res, tree[l++]);
            if (r % 2 == 0) res = max(res, tree[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> H[i] >> A[i] >> B[i];
    }
    
    // 预处理所有通信对
    for (int x = 1; x <= N; x++) {
        int start_y = x + A[x];
        int end_y = min(x + B[x], N);
        if (start_y > end_y) continue;
        
        for (int y = start_y; y <= end_y; y++) {
            // 检查 y 是否能与 x 通信
            int dist = y - x;
            if (dist >= A[y] && dist <= B[y]) {
                pairs.emplace_back(x, y, abs(H[x] - H[y]));
            }
        }
    }
    
    // 按 y 坐标排序通信对
    sort(pairs.begin(), pairs.end(), [](const Pair& a, const Pair& b) {
        return a.y < b.y;
    });
    
    cin >> Q;
    ans.assign(Q, -1);
    vector<Query> queries;
    
    for (int i = 0; i < Q; i++) {
        int L, R;
        cin >> L >> R;
        queries.emplace_back(L, R, i);
    }
    
    // 按 R 坐标排序查询
    sort(queries.begin(), queries.end());
    
    // 离线处理
    SegmentTree st(N);
    int pair_ptr = 0;
    
    for (const Query& q : queries) {
        // 将所有 y <= q.R 的通信对加入线段树
        while (pair_ptr < pairs.size() && pairs[pair_ptr].y <= q.R) {
            st.update(pairs[pair_ptr].x, pairs[pair_ptr].cost);
            pair_ptr++;
        }
        
        // 查询 [q.L, q.R-1] 范围内的最大值
        ans[q.idx] = st.query(q.L, q.R - 1);
    }
    
    for (int a : ans) {
        cout << a << "\n";
    }
    
    return 0;
}