#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int n, q; int h[maxn], a[maxn], b[maxn]; pair<int, int> queries[maxn]; namespace subtask12 { bool check() {return n <= 2000;} void solve() { vector<vector<int>> L(n+1, vector<int>(n+1, -1)); for (int i = 1; i <= n; ++i) { if (i+a[i] > n) continue; for (int j = i+a[i]; j <= min(n, i+b[i]); ++j) { L[i][j] = L[i][j-1]; if (j-b[j] <= i && i <= j-a[j]) L[i][j] = max(L[i][j], abs(h[i] - h[j])); } for (int j = i+b[i]+1; j <= n; ++j) L[i][j] = L[i][j-1]; } vector<vector<int>> ans(n+1, vector<int>(n+1, -1)); for (int i = 1; i <= n; ++i) { for (int j = i-1; j >= 1; --j) ans[j][i] = max(ans[j+1][i], L[j][i]); } for (int i = 1; i <= q; ++i) cout << ans[queries[i].first][queries[i].second] << '\n'; } } namespace subtask3 { bool check() {return q == 1 && queries[1].first == 1 && queries[1].second == n;} struct evt { int pos, idx, type; }; struct SMT { vector<int> st; SMT(int n): st(4*n, -1) {} void upd(int id, int l, int r, int u, int val) { if (l == r) { st[id] = val; return ; } int mid = (l + r) >> 1; if (u <= mid) upd(id << 1, l, mid, u, val); else upd(id << 1 | 1, mid + 1, r, u, val); st[id] = max(st[id << 1], st[id << 1 | 1]); } int get(int id, int l, int r, int u, int v) { if (r < u || l > v) return -1; if (u <= l && r <= v) return st[id]; int mid = (l + r) >> 1; return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } }; int right() { SMT seg(n); vector<evt> events; for (int i = 1; i <= n; ++i) { events.push_back({i+a[i], i, 1}); events.push_back({i+b[i]+1, i, 0}); } sort(events.begin(), events.end(), [](evt &a, evt &b) {return a.pos < b.pos;}); int j = 0; int res = -1; for (int i = 1; i <= n; ++i) { while (j < events.size() && events[j].pos <= i) { if (events[j].type) seg.upd(1, 1, n, events[j].idx, h[events[j].idx]); else seg.upd(1, 1, n, events[j].idx, -1); ++j; } if (i-a[i] < 1) continue; int idfk = seg.get(1, 1, n, max(1, i-b[i]), i-a[i]); if (idfk != -1) res = max(res, idfk - h[i]); } return res; } int left() { SMT seg(n); vector<evt> events; for (int i = 1; i <= n; ++i) { events.push_back({i-a[i], i, 1}); events.push_back({i-b[i]-1, i, 0}); } sort(events.begin(), events.end(), [](evt &a, evt &b) {return a.pos > b.pos;}); int j = 0; int res = -1; for (int i = n; i >= 1; --i) { while (j < events.size() && events[j].pos >= i) { if (events[j].type) seg.upd(1, 1, n, events[j].idx, h[events[j].idx]); else seg.upd(1, 1, n, events[j].idx, -1); ++j; } if (i+a[i] > n) continue; int idfk = seg.get(1, 1, n, i+a[i], min(n, i+b[i])); if (idfk != -1) res = max(res, idfk - h[i]); } return res; } void solve() { cout << max(left(), right()); } } namespace subtask4 { struct evt { int pos, idx, type; }; struct node { int maxval, minval, best; node(int p1 = 0, int p2 = 0, int p3 = -1): maxval(p1), minval(p2), best(p3) {} node operator+ (const node &other) { if (maxval == 0 && other.maxval != 0) return other; if (maxval != 0 && other.maxval == 0) return *this; return node(max(maxval, other.maxval), min(minval, other.minval), max(best, other.best)); } }; struct SMT { vector<node> st; vector<pair<int, int>> lz; SMT(int n): st(4*n+5), lz(4*n+5, {0, INT_MAX}) {} void push(int id, int l, int r) { if (lz[id].first == 0 && lz[id].second == INT_MAX) return ; st[id].best = max({st[id].best, abs(lz[id].first-st[id].minval), abs(lz[id].second-st[id].maxval)}); if (l != r) { int mid = (l + r) >> 1; if (st[id << 1].maxval != 0 && st[id << 1].minval != 0) { lz[id << 1].first = max(lz[id << 1].first, lz[id].first); lz[id << 1].second = min(lz[id << 1].second, lz[id].second); push(id << 1, l, mid); } if (st[id << 1 | 1].maxval != 0 && st[id << 1 | 1].minval != 0) { lz[id << 1 | 1].first = max(lz[id << 1 | 1].first, lz[id].first); lz[id << 1 | 1].second = min(lz[id << 1 | 1].second, lz[id].second); push(id << 1 | 1, mid+1, r); } } lz[id] = {0, INT_MAX}; } void ptupd(int id, int l, int r, int u, int val) { push(id, l, r); if (l == r) { st[id].maxval = st[id].minval = val; return ; } int mid = (l + r) >> 1; if (u <= mid) ptupd(id << 1, l, mid, u, val); else ptupd(id << 1 | 1, mid+1, r, u, val); st[id] = st[id << 1] + st[id << 1 | 1]; } void rangeupd(int id, int l, int r, int u, int v, int val) { push(id, l, r); if (r < u || l > v) return ; if (u <= l && r <= v) { if (st[id].maxval == 0 && st[id].minval == 0) return ; lz[id].first = max(lz[id].first, val); lz[id].second = min(lz[id].second, val); push(id, l, r); return ; } int mid = (l + r) >> 1; rangeupd(id << 1, l, mid, u, v, val); rangeupd(id << 1 | 1, mid+1, r, u, v, val); st[id] = st[id << 1] + st[id << 1 | 1]; } int query(int id, int l, int r, int u, int v) { push(id, l, r); if (r < u || l > v) return -1; if (u <= l && r <= v) return st[id].best; int mid = (l + r) >> 1; return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid+1, r, u, v)); } }; void solve() { vector<evt> events; vector<pair<pair<int, int>, int>> qe(q); vector<int> ans(q); for (int i = 1; i <= n; ++i) { events.push_back({i, i, 2}); events.push_back({i+a[i], i, 1}); events.push_back({i+b[i]+1, i, 0}); } for (int i = 0; i < q; ++i) { qe[i] = {queries[i+1], i}; } sort(qe.begin(), qe.end(), [](pair<pair<int, int>, int> &p1, pair<pair<int, int>, int> &p2) {return p1.first.second < p2.first.second;}); sort(events.begin(), events.end(), [](evt &e1, evt &e2) {return (e1.pos == e2.pos ? e1.type < e2.type : e1.pos < e2.pos);}); SMT seg(n); int j = 0; for (int i = 0; i < q; ++i) { while (j < events.size() && events[j].pos <= qe[i].first.second) { //upd seg int idx = events[j].idx, type = events[j].type; // cout << events[j].pos << ' ' << idx << ' ' << type << '\n'; if (type == 0) { // cout << "deactivating node " << idx << '\n'; seg.ptupd(1, 1, n, idx, 0); } else if (type == 1) { // cout << "activating node " << idx << '\n'; seg.ptupd(1, 1, n, idx, h[idx]); } else { // cout << "updating nodes [" << max(1, idx-b[idx]) << ", " << max(1, idx-a[idx]) << "]\n"; seg.rangeupd(1, 1, n, max(1, idx-b[idx]), max(1, idx-a[idx]), h[idx]); // cout << "current tree: "; // for (int k = 1; k <= n; ++k) cout << seg.query(1, 1, n, k, k) << ' '; // cout << '\n'; } ++j; } ans[qe[i].second] = seg.query(1, 1, n, qe[i].first.first, qe[i].first.second);// range maximium/minimum query; } for (auto i : ans) cout << i << ' '; } } 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]; } cin >> q; for (int i = 1; i <= q; ++i) cin >> queries[i].first >> queries[i].second; // if (subtask12::check()) subtask12::solve(); // else if (subtask3::check()) subtask3::solve(); subtask4::solve(); return 0; }