56 E Domino Principle

問題

ドミノが一列に並んでいて、それぞれのx座標x[i]および高さh[i]が与えられる。
x座標xにあるドミノを倒すと、x座標x+1以上x+h-1以下のドミノが全て倒れる。
ドミノ倒しは連鎖する。

i番目のドミノを倒したときに倒れるドミノの数をそれぞれ求めよ。

制約条件

n≦10^5
-10^8 ≦x[i]≦10^8
2 ≦ h ≦10^8

方針

まずはドミノをx座標の順にソート。
右からドミノを見ていく。

i番目のドミノが倒れたときに、「右にあって倒れない最も左側のドミノ」を覚えておく。

i番目のドミノを倒したときに、そのドミノが直接倒すドミノは二分探索によりわかる。
直接倒すドミノが、どのくらい右側のドミノを倒すかは、倒れる範囲のドミノにおける上の記録値の最大値を見てやればいい。

これはsegment treeによりO(log n)で求まる。
スタックを使う別解があるっぽい。

ソースコード

const int MX=131072;
int n, N,dat[2*MX-1];
pi p[100000],q[100000];

void update(int k,int a){
	k+=N-1;
	dat[k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[k]=max(dat[k*2+1],dat[k*2+2]);
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<=a||b<=l)return 0;
	if(a<=l&&r<=b)return dat[k];
	return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
}

void run()
{
	cin>>n;
	rep(i,n)cin>>p[i].first>>p[i].second, q[i]=p[i], q[i].second=i;
	sort(p,p+n); sort(q,q+n);
	
	N=1;
	while(N<n)N*=2;
	rep(i,2*N-1)dat[i]=0;
	
	vi ans(n);
	for(int i=n-1;i>=0;i--){
		int mx=lower_bound(p,p+n,pi(p[i].first+p[i].second,0))-p;
		mx=max(mx,query(i+1,mx,0,0,N));
		update(i,mx);
		ans[q[i].second]=mx-i;
	}
	rep(i,n)cout<<ans[i]<<" "; cout<<endl;
}