Problem DescriptionVasya很喜欢排多米诺骨牌。他已经厌倦了普通的多米诺骨牌，所以他用不同高度的多米诺骨牌。他从左边到右边，把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 Sample Output|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108 |
// 这题我们很容易想到应该是先对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-6using
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 ;} |
fzoj 2163 多米诺骨牌,布布扣,bubuko.com
原文：http://www.cnblogs.com/20120125llcai/p/3664556.html