BSNY正在玩多米诺骨牌，他将n块多米诺骨牌从左到右排成一行。其中每块多米诺骨牌所在的位置设为x，每块多米诺骨牌高度为h。如果将x位置上的多米诺骨牌向右翻到，它就可以影响[x+1, x+h-1]范围内的所有多米诺骨牌，让他们也翻到，同时这些被翻到的多米诺骨牌还能影响到其他多米诺骨牌，也就是多米诺骨牌效应。
例如现在有4块多米诺骨牌，位置从左到右依次为10 16 18 20，它们的高度依次为10, 5, 2, 5。当翻到16位置上的多米诺骨牌，18和20位置都在范围[16+1, 16+5-1]，所以这两块也翻到了，总共翻到了3块。
现在BSNY给出n块多米诺骨牌的位置和高度，问如果向右翻到第i块多米诺骨牌，会有多少多米诺骨牌翻到。
输入
第一行输入n
接下来n行每行输入xi和hi，分别表示第i块多米诺骨牌的位置和高度
输出
输出一行包含n个结果，用空格隔开
第i个结果表示如果向右翻到第i块多米诺骨牌，会有多少多米诺骨牌翻到。
样例输入
4
16 5
20 5
10 10
18 2
样例输出
3 1 4 1
提示
【样例说明】
输入：
4
0 10
1 5
9 10
15 10
输出：
4 1 2 1
【数据规模和约定】
1<=n<=10^5, -10^8<=xi<=10^8 , 2<=hi<=10^8 xi都不一样
********************************************************************
solution：相信大家都会n^2的暴力，但这无疑会超时。现在我们的一个瓶颈是：怎么快速计算？那么势必要成片累加。我们可以记录下每个点往后能够连续推倒的数量，只要它在范围内，就可以累加这个值，然后直接跳过已被覆盖的点。这样就可以大大节约时间（虽然仍有一部分常数），考试的时候我也是想到这种边扩展边累加的方法，但是没想到用dp的方式来记录并累加，所以就超了。。。。。
#include<cstdio>#include<iostream>#include<algorithm>#define p1 id<<1#define p2 id<<1^1using namespace std;int n;int ans[100005];int tree[450000];struct ty{int x,h,id,to;}d[100005];bool cmp(ty a,ty b){return a.x<b.x;}int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&d[i].x,&d[i].h);d[i].id=i;d[i].to=d[i].x+d[i].h-1;}sort(d+1,d+n+1,cmp);ans[d[n].id]=1;for(int i=n-1;i>=1;i--) {int last=d[i].to;int q=i+1;ans[d[i].id]=1;while(0==0){if(q>n) break;if(d[q].x<=last) ans[d[i].id]+=ans[d[q].id]; //为什么不用更新last，因为我在当前点能到的范围之外的点，要是能推倒的话，肯定已经包括在当前范围里的某个点中else break;q=q+ans[d[q].id];}} for(int i=1;i<n;i++) cout<<ans[i]<<' ';cout<<ans[n]<<endl;return 0;}
