CodeForces 500E New Year Domino

题意：

从左到右排列着(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("%dn", ans);
}
return 0;
}