【题解】CF56E

Link

题意简述：给你一些多米诺骨牌，在 $x$ 轴上从左到右排列在一起，问每一个倒向右边的时候会压倒多少个骨牌？

首先按坐标升序排序

从后往前维护 $to_i$，表示第 $i$ 个骨牌能推到的最远的骨牌的编号。

二分这个骨牌自己能推到的最远的骨牌，设这个骨牌为 $j$ ，则 $to_i=\max\limits_{i < k \le j}(to_k)$ ，显然可以用线段树维护。

时间复杂度$\mathcal{O(n \log n)}$

看起来比其他题解菜很多但是 又 不 是 不 能 A

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=100005;
int n;
struct point{
	int pos,h,id;
	bool operator<(point b){
		return pos<b.pos;
	}
}tmp[MAXN];
int a[MAXN],h[MAXN];
int to[MAXN];
int ans[MAXN];

struct Segment_Tree{
	// const int INF=0x3f3f3f3f;
	struct node{
		int l,r,len;
		int add,v,mx;
	}st[MAXN*4];
	
	void build(int p,int l,int r){
		st[p].l=l;st[p].r=r;
		st[p].len=r-l+1;
		if (l==r){
			// st[p].v=a[l];
			st[p].mx=0;
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		st[p].v=st[p<<1].v+st[p<<1|1].v;
		st[p].mx=max(st[p<<1].mx,st[p<<1|1].mx);
	}

	void spread(int p){
		// st[p<<1].v+=st[p].add*st[p<<1].len;
		// st[p<<1|1].v+=st[p].add*st[p<<1|1].len;
		st[p<<1].add+=st[p].add;
		st[p<<1|1].add+=st[p].add;
		st[p<<1].mx+=st[p].add;
		st[p<<1|1].mx+=st[p].add;
		st[p].add=0;
	}

	void change(int p,int l,int r,int c){
		if (l<=st[p].l&&st[p].r<=r){
			// st[p].v+=c*st[p].len;
			st[p].add+=c;
			st[p].mx+=c;
			return;
		}
		spread(p);
		int mid=st[p].l+st[p].r>>1;
		if (l<=mid) change(p<<1,l,r,c);
		if (r>mid) change(p<<1|1,l,r,c);
		// st[p].v=st[p<<1].v+st[p<<1|1].v;
		st[p].mx=max(st[p<<1].mx,st[p<<1|1].mx);
	}

	int query_max(int p,int l,int r){
		if (l<=st[p].l && st[p].r<=r)
			return st[p].mx;
		spread(p);
		int mid=st[p].l+st[p].r>>1,ans=0;
		if (l<=mid) ans=query_max(p<<1,l,r);
		if (r>mid) ans=max(ans,query_max(p<<1|1,l,r));
		return ans;
	}
}seg;

int main()

{
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>tmp[i].pos>>tmp[i].h;
		tmp[i].id=i;
	}

	sort(tmp+1,tmp+1+n);

	for (int i=1;i<=n;i++){
		a[i]=tmp[i].pos;
		h[i]=tmp[i].h;
	}

	seg.build(1,1,n);
	to[n]=n;
	ans[tmp[n].id]=1;
	seg.change(1,n,n,n);
	for (int i=n-1;i>=1;i--){
		int l=i,r=n,goal=a[i]+h[i]-1;
		while (l<=r){
			int mid=l+r>>1;
			if (a[mid]<=goal) l=mid+1;
			else r=mid-1;
		}
		to[i]=max(i,seg.query_max(1,i,r));
		seg.change(1,i,i,to[i]);
		ans[tmp[i].id]=to[i]-i+1;
	}

	for (int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}