题意：
从左到右排列着\(n\)个多米诺骨牌，它们分别站在\(x\)轴上的位置\(p_i\)上且高度为\(l_i\)。
当第\(i\)个多米诺骨牌向右倒下时，如果\(p_i < p_j \leq p_i + l_i\)那么第\(j\)个多米诺骨牌也会倒下，以此类推。
然后有\(q\)个询问\([x, \, y]\)，要推倒第\(x\)个多米诺骨牌，而且最终要使得第\(y\)个多米诺骨牌倒下。
为了使第\(y\)个倒下，可以加长某些牌的长度。
对于每个询问，求最少加长的总长度之和。
分析：
对于第\(i\)个牌，定义\(R_i\)为推倒第\(i\)个牌，所倒下的牌中\(p_j+l_j\)的最大值。
有递推式：\(R_i=max \{ p_i+l_i, \, max\{ R_j | p_i < p_j \leq p_i+l_i \} \}\)
\(R_i\)可以通过维护线段树计算得到。
接下来根据\(R_i\)计算\(U_i\)，表示推倒第\(i\)个牌后，最左边没有倒下的牌的编号。
因此从\(x\)到\(U_x\)，我们至少需要增加\(p_{U_{x}} - R_x\)的长度。
所以我们向右一步一步地加，直到第\(y\)块倒下为止。
但是这样每次查询的复杂度为\(O(n)\)的。
所以还需要二进制优化一下，类似于求\(LCA\)的倍增算法。
\(anc(i, \, j)\)表示迭代\(2^j\)次\(U_i\)最后得到的牌的编号，\(cost(i, \, j)\)表示相应增加的牌的长度。
\(O(nlogn)\)预处理一下，就可以做到\(O(logn)\)查询。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200000 + 10;
int n, q;
int p[maxn], l[maxn];
int R[maxn], U[maxn];
int maxv[maxn << 2];
void update(int o, int L, int R, int p, int v) {
if(L == R) { maxv[o] = v; return; }
int M = (L + R) / 2;
if(p <= M) update(o<<1, L, M, p, v);
else update(o<<1|1, M+1, R, p, v);
maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
}
int query(int o, int L, int R, int qL, int qR) {
if(qL <= L && R <= qR) { return maxv[o]; }
int M = (L + R) / 2;
int ans = 0;
if(qL <= M) ans = max(ans, query(o<<1, L, M, qL, qR));
if(qR > M) ans = max(ans, query(o<<1|1, M+1, R, qL, qR));
return ans;
}
int anc[maxn][20], cost[maxn][20];
int lb(int l, int r, int x) {
while(l < r) {
int mid = (l + r) / 2 + 1;
if(p[mid] <= x) l = mid;
else r = mid - 1;
}
return l;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d%d", p + i, l + i);
for(int i = n; i; i--) {
R[i] = p[i] + l[i];
int lft = i + 1;
int rgh = lb(1, n, p[i] + l[i]);
if(lft <= rgh) R[i] = max(R[i], query(1, 1, n, lft, rgh));
update(1, 1, n, i, R[i]);
}
for(int i = 1; i <= n; i++) {
U[i] = upper_bound(p + 1, p + 1 + n, R[i]) - p;
if(U[i] == n + 1) U[i]--;
}
for(int i = 1; i <= n; i++) {
anc[i][0] = U[i];
cost[i][0] = max(0, p[U[i]] - R[i]);
}
for(int j = 1; (1 << j) < n; j++)
for(int i = 1; i <= n; i++) if(anc[i][j-1] != n) {
int t = anc[i][j-1];
anc[i][j] = anc[t][j-1];
cost[i][j] = cost[i][j-1] + cost[t][j-1];
}
scanf("%d", &q);
while(q--) {
int x, y; scanf("%d%d", &x, &y);
int ans = 0;
for(int i = 19; i >= 0; i--) if(anc[x][i] && anc[x][i] <= y) {
ans += cost[x][i];
x = anc[x][i];
}
if(x < y) ans += max(0, p[y] - p[U[x]]);
printf("%d\n", ans);
}
return 0;
}