先用线段树处理出推倒某一个后能覆盖到的最右端的位置R（绝对不能是最右边的那个骨牌，因为有可能右面的很短，左面的巨长(R不随L单调)，后面算花费又需要用到这个位置），之后可以花费R到第一个比R大的左端点来跳到下一个骨牌
然后可以倍增处理出跳多少次能跳到哪个骨牌，统计答案即可
1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define CLR(a,x) memset(a,x,sizeof(a)) 4 using namespace std; 5 typedef long long ll; 6 const int maxn=2e5+10; 7 8 inline ll rd(){ 9 ll x=0;char c=getchar();int neg=1; 10 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12 return x*neg; 13 } 14 15 int N,M,L[maxn],R[maxn],R1[maxn],nxtp[maxn]; 16 int rma[maxn*4],ch[maxn*4],nxt[maxn][20],dis[maxn][20]; 17 18 inline void update(int p){ 19 rma[p]=max(rma[p<<1],rma[p<<1|1]); 20 } 21 22 void change(int p,int l,int r,int x,int y){ 23 if(l==r) rma[p]=y; 24 else{ 25 int m=l+r>>1; 26 if(x<=m) change(p<<1,l,m,x,y); 27 else change(p<<1|1,m+1,r,x,y); 28 update(p); 29 } 30 } 31 int query(int p,int l,int r,int x,int y){ 32 if(x<=l&&r<=y) 33 return rma[p]; 34 else{ 35 int m=l+r>>1,re=0; 36 if(x<=m) re=query(p<<1,l,m,x,y); 37 if(y>=m+1) re=max(re,query(p<<1|1,m+1,r,x,y)); 38 return re; 39 } 40 } 41 42 int main(){ 43 //freopen("","r",stdin); 44 int i,j,k; 45 N=rd(); 46 for(i=1;i<=N;i++){ 47 L[i]=rd(),R[i]=rd()+L[i]; 48 } 49 L[N+1]=2e9+1; 50 for(i=1;i<=N;i++){ 51 nxtp[i]=upper_bound(L+1,L+N+2,R[i])-L-1; 52 } 53 for(i=N;i;i--){ 54 R1[i]=max(R[i],query(1,1,N,i,nxtp[i])); 55 change(1,1,N,i,R1[i]); 56 nxt[i][0]=upper_bound(L+1,L+N+2,R1[i])-L; 57 if(nxt[i][0]<=N){ 58 dis[i][0]=L[nxt[i][0]]-R1[i]; 59 for(j=0;nxt[i][j]&&nxt[nxt[i][j]][j];j++){ 60 nxt[i][j+1]=nxt[nxt[i][j]][j]; 61 dis[i][j+1]=dis[i][j]+dis[nxt[i][j]][j]; 62 } 63 }else nxt[i][0]=0; 64 } 65 M=rd(); 66 for(i=1;i<=M;i++){ 67 int a=rd(),b=rd(),ans=0; 68 69 for(j=18;j>=0;j--){ 70 if(nxt[a][j]&&nxt[a][j]<=b) 71 ans+=dis[a][j],a=nxt[a][j]; 72 } 73 printf("%d ",ans); 74 } 75 return 0; 76 }