原题地址
题目描述
给定一列多米诺骨牌的高度和底端横坐标，求若要让推动第x块至少使第y块倒下，需要加长区间内的多米诺骨牌的总长度。
样例
输入
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6输出
0
1
1
2样例解释
（样例的第四个询问）
思路
倍增。
维护一块骨牌右边最近的碰不到的骨牌编号和距离。
询问直接log累加就行了。。。
代码
#include
#define maxn 200010
using namespace std;
long long p[maxn][30],d[maxn][30],q[maxn];
long long n,a[maxn],b[maxn],fr;
int main(){
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i]>>b[i];
q[++fr]=n+1;a[n+1]=0x777777777777777,b[n+1]=0;
p[n+1][0]=n+1,d[n+1][0]=0;
for (int i=n;i>=1;i--){
while(a[q[fr]]+b[q[fr]]<=a[i]+b[i]) fr--;
p[i][0]=q[fr];
d[i][0]=max((long long)0,a[q[fr]]-a[i]-b[i]);q[++fr]=i;
}
for (int i=1;i<30;i++)
for (int x=n+1;x>0;x--){
p[x][i]=p[p[x][i-1]][i-1];
d[x][i]=d[x][i-1]+d[p[x][i-1]][i-1];
}
int TAT;cin>>TAT;while(TAT--){
int l,r,ans=0;cin>>l>>r;
for (int i=29;i>=0;i--)
if (p[l][i]<=r) ans+=d[l][i],l=p[l][i];
cout<