Problem 2163 多米诺骨牌
Accept: 10 Submit: 32
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
Vasya很喜欢排多米诺骨牌。他已经厌倦了普通的多米诺骨牌，所以他用不同高度的多米诺骨牌。他从左边到右边，把n个多米诺骨牌沿一个轴放在桌子上。每一个多米诺骨牌垂直于该轴，使该轴穿过其底部的中心。第i个多米诺骨牌具有坐标xi与高度hi。现在Vasya想要知道，对于每一个多米诺骨牌如果他推倒的话，右侧会有多少个多米诺骨牌也会倒下。
想想看，一个多米诺倒下，如果它严格的触动右侧的多米诺骨牌，被触碰的也会倒下。换句话说，如果多米诺骨牌（初始坐标x和高度h）倒下，会导致所有在[ X + 1，x + H - 1]范围内的多米诺骨牌倒下。
Input
输入有多组测试数据，处理到文件结尾。
每组测试数据第一行包含整数n(1≤N≤10^5)，这是多米诺骨牌的数量。然后n行，每行包含两个整数xi与hi(-10^8≤xi≤10^8 ,2 ≤hi≤108），xi表示多米诺骨牌的坐标和hi表示多米诺骨牌的高度。没有两个多米诺骨牌在同一个坐标点上。
Output
对于每组数据输出一行，包含n个空格分隔的数Zi - 表示倒下的多米诺骨牌数量，如果Vasya推第i个多米诺骨牌（包括多米诺骨牌本身）。
Sample Input
4 16 5 20 5 10 10 18 2 3 6 7 2 9 -6 10
Sample Output
3 1 4 1 1 2 3
// 这题我们很容易想到应该是先对x排序，然后再求出结果
// 对 x 排序后，我们从x 最大的开始往前推答案
// 对于 第 i 个 对于 他能覆盖的居间内 的 j , i < j
// ans[j] 就是 j 能推到的最大数目 则 ans[i] = max(ans[j]+j-i-1)+1 ; +1 是它自己本身也要倒
// 即 ans[i] = max(ans[j]+j) - i ; 这样我们可以用线段树维护 ans[j]+j
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <cstring>
#include <set>
#include <stack>
#include <string>
#define LL long long
#define maxn 100010
#define mod 1010
#define INF 10000000
#define MAX 20009
#define eps 1e-6
using namespace std;
struct node
{
int x , h ,id ;
bool operator <( const node &s) const{
return x < s.x ;
}
}qe[maxn] ;
int _max[maxn*3] ;
int ql,qr ,v ,ans[maxn];
void update( int L ,int R , int o)
{
if(L==R)
{
_max[o] = v;
return ;
}
int mid = (L+R)>>1;
if(ql <= mid) update(L,mid,o<<1) ;
else update(mid+1,R,o<<1|1) ;
if(_max[o<<1] > _max[o<<1|1]) _max[o] = _max[o<<1] ;
else _max[o] = _max[o<<1|1] ;
}
void find( int L , int R ,int o)
{
if( ql <= L && qr >= R )
{
if(_max[o] > v ) v = _max[o] ;
return ;
}
int mid = (L+R)>>1 ;
if(ql <= mid) find(L,mid,o<<1) ;
if(qr > mid) find(mid+1,R,o<<1|1) ;
}
int find1( int x , int n )
{
int L ,R ,mid ;
// 二分求出能覆盖的居间，
if(x >= qe[n].x) return n ;
L = 1 ;R = n ;
while( L <= R )
{
mid = (L+R)>>1 ;
if(qe[mid].x > x ) R = mid-1 ;
else L = mid+1 ;
}
return R ;
}
int main()
{
int i , n , m, j , k ;
// freopen("in.txt","r",stdin) ;
while( scanf("%d",&n) != EOF )
{
for( i = 1 ; i <= n ;i++ ){
scanf("%d%d",&qe[i].x,&qe[i].h) ;
qe[i].id = i ;
}
sort(qe+1,qe+1+n) ;
ql = n ;
v = n+1 ;
ans[qe[n].id] = 1 ;
update(1,n,1) ;
for( i = n-1 ; i >= 1 ;i--)
{
v = -INF ;
ql = i+1 ;
qr = find1(qe[i].x+qe[i].h-1,n);
if(qr >= ql)
find(1,n,1) ;
ans[qe[i].id] = (v==-INF ? 1:v-i);
ql = i ;
v = ans[qe[i].id]+i ;
update(1,n,1) ;
}
cout << ans[1] ;
for( i = 2 ; i <= n ;i++ )
printf(" %d",ans[i]) ;
puts("") ;
}
return 0 ;
}