### 题目描述

#### 样例

##### 输入
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

（样例的第四个询问）

### 代码

#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<
 
 Share 【CodeForces 456D】A Lot of Games / 题解 原题地址 [https://codeforces.com/problemset/problem/456/D] 题目描述 给定n个小写字母组成的字符串，有两个人用这些字符串玩游戏。游戏内容是轮流在一个空串末尾添加一个小写字母，… 18 Jul 2018 【影评】Puta 不是 Buddha Onedrive 下载 [https://drive.xgzepto.cn/%E7%A7%81%E8%B4%A7/… 15 Jul 2018 
 
 
 Zepto's © 2024 Data & privacy Contact → Published with Ghost • Theme Attila • System theme 
 $(document).ready(function () { var viewport =$(window); var post = $('.post-content'); // Responsive videos with fitVids post.fitVids(); // Format code blocks and add line numbers function codestyling() {$('pre code').each(function(i, e) { // Code highlight hljs.highlightElement(e); // No lines for plain text blocks if (!$(this).hasClass('language-text')) { var code =$(this); // Calculate amount of lines var lines = code.html().split(/\n(?!$)/g).length; var numbers = []; if (lines > 1) { lines++; } for (i = 1; i < lines; i++) { numbers += '<span class="line" aria-hidden="true">' + i + '</span>'; } code.parent().append('<div class="lines">' + numbers + '</div>'); } }); } codestyling(); // Reading progress bar on window top function readingProgress() { var postBottom = post.offset().top + post.height(); var viewportHeight = viewport.height(); var progress = 100 - (((postBottom - (viewport.scrollTop() + viewportHeight) + viewportHeight / 3) / (postBottom - viewportHeight + viewportHeight / 3)) * 100);$('.progress-bar').css('width', progress + '%'); (progress > 100) ? $('.progress-container').addClass('complete'):$('.progress-container').removeClass('complete'); } readingProgress(); // Trigger reading progress viewport.on({ 'scroll': function() { readingProgress(); }, 'resize': function() { readingProgress(); }, 'orientationchange': function() { readingProgress(); } }); });