【SNOI2017】炸弹

在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi , 爆炸半径是 Ri
当一个炸弹爆炸时，如果另一个炸弹在其爆炸范围内，那么，该炸弹也会被引爆
现在，请你帮忙计算一下，先把第 i 个炸弹引爆，将引爆多少个炸弹呢？
答案对1000000007取模

要求输出的是 (sum_{i=1}^{n} i*ans[i])

这么经典的线段树优化建边，居然现在才做……
而且搞的还是玄学方法，每次lower_bound和upper_bound找其单独能炸到的所有炸弹
然后用一棵线段树来维护……

代码：

#include<bits/stdc++.h>
#define LL long long
#define mod 1000000007
#define mid ((l+r)>>1)
#define N 500005
#define M 1000005
using namespace std;

LL n,x[N],r[N],lef[N],rig[N];
LL tl[N<<2],tr[N<<2];
LL xx,yy,ll,rr;
LL ans=0;

template<class T>inline void read(T &res)
{
	char c;T flag=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
	while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

void build(LL rt,LL l,LL r)
{
	if(l==r)
	{
		tl[rt]=lef[l];
		tr[rt]=rig[r];
		return;
	}
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	tl[rt]=min(tl[rt<<1],tl[rt<<1|1]);
	tr[rt]=max(tr[rt<<1],tr[rt<<1|1]);
}

void query(LL rt,LL l,LL r,LL x,LL y)
{
	if(l>=x&&r<=y)
	{
		ll=min(ll,tl[rt]);
		rr=max(rr,tr[rt]);
		return;
	}
	if(x<=mid) query(rt<<1,l,mid,x,y);
	if(y>mid) query(rt<<1|1,mid+1,r,x,y);
}

int main()
{
	read(n);
	for(register int i=1;i<=n;++i) read(x[i]),read(r[i]);
	for(register int i=1;i<=n;++i)
	{
		lef[i]=lower_bound(x+1,x+i,x[i]-r[i])-x;
		rig[i]=upper_bound(x+i+1,x+n+1,x[i]+r[i])-x-1;
	}
	build(1,1,n);
	for(register int i=1;i<=n;++i)
	{
		xx=yy=ll=rr=i;
		query(1,1,n,xx,yy);
		while(ll!=xx||rr!=yy)
		{
			xx=ll;
			yy=rr;
			query(1,1,n,xx,yy);
		}
		ans=(LL)(ans+i*(yy-xx+1)%mod)%mod;
	}
	printf("%lld
",ans);
	return 0;
}