线段树优化建图+Tarjan+DP，LOJ AC，洛谷WA test#1, 2 86pts

代码:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int mod=1000000007;
void read(ll &x){
	x=0;char c=getchar();bool ne=false;
	while(!isdigit(c))ne|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(ne)x=-x;
}
const int N=500000,NOW=N<<2,M=N*20;
int n;
struct bomb{ll x,r;}a[N+1];
bool operator<(bomb x,bomb y){return x.x<y.x;}
int now;
struct addedge{
	int sz,head[NOW+1],nxt[M+1],val[M+1];
	void init(){sz=0;memset(head,0,sizeof(head));}
	void ae(int x,int v){
		nxt[++sz]=head[x];val[sz]=v;head[x]=sz;
	}
}nei;
struct segtree{
	struct node{int l,r,nd;}nd[N<<2];
	#define l(p) nd[p].l
	#define r(p) nd[p].r
	#define nd(p) nd[p].nd
	void bld(int l=1,int r=n,int p=1){
		l(p)=l;r(p)=r;
		if(l==r)return nd(p)=l,void();
		nd(p)=++now;
		int mid=l+r>>1;
		bld(l,mid,p<<1);bld(mid+1,r,p<<1|1);
		nei.ae(nd(p),nd(p<<1));nei.ae(nd(p),nd(p<<1|1));
	}
	void init(){bld();}
	void ae(int l,int r,int v,int p=1){
		if(l<=l(p)&&r>=r(p))return nei.ae(v,nd(p)),void();
		int mid=l(p)+r(p)>>1;
		if(l<=mid)ae(l,r,v,p<<1);
		if(r>mid)ae(l,r,v,p<<1|1);
	} 
}segt;
int dfn[NOW+1],low[NOW+1],nowdfn;
int stk[NOW],top;
bool ins[NOW+1];
vector<vector<int> > scc;
int cid[NOW+1];
void dfs(int x){
	dfn[x]=low[x]=++nowdfn;
	ins[stk[top++]=x]=true;
	for(int i=nei.head[x];i;i=nei.nxt[i]){
		int y=nei.val[i];
		if(!dfn[y])dfs(y),low[x]=min(low[x],low[y]);
		else if(ins[y])low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		scc.pb(vector<int>());
		while(true){
			int y=stk[--top];
			ins[y]=false;
			scc.back().pb(y);cid[y]=scc.size()-1;
			if(y==x)break;
		}
	}
}
addedge cnei;
int dp[NOW];
bool vis[NOW];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)read(a[i].x),read(a[i].r);
	now=n;
	nei.init();
	segt.init();
	for(int i=1;i<=n;i++){
		int l=lower_bound(a+1,a+n+1,bomb({a[i].x-a[i].r,0}))-a,r=upper_bound(a+1,a+n+1,bomb({a[i].x+a[i].r,0}))-1-a;
		segt.ae(l,r,i);
	}
	for(int i=1;i<=now;i++)if(!dfn[i])dfs(i);
	cnei.init();
	for(int i=1;i<=now;i++)for(int j=nei.head[i];j;j=nei.nxt[j]){
		int x=nei.val[j];
		if(cid[i]!=cid[x])cnei.ae(cid[i],cid[x]);
	}
	int ans=0;
	for(int i=0;i<scc.size();i++){
		vector<int> &v=scc[i];
//		printf("scc#%d=",i);for(int j=0;j<v.size();j++)cout<<v[j]<<" ";puts("");
		int sum=0;
		for(int j=0;j<v.size();j++)if(v[j]<=n)dp[i]++,(sum+=v[j])%=mod;
		for(int j=cnei.head[i];j;j=cnei.nxt[j]){
			int x=cnei.val[j];
			if(!vis[x])vis[x]=true,dp[i]+=dp[x];
		}
//		printf("dp=%d\n",dp[i]);
		(ans+=1ll*dp[i]*sum%mod)%=mod;
		for(int j=cnei.head[i];j;j=cnei.nxt[j])vis[cnei.val[j]]=false;
	}
	cout<<ans;
	return 0;
}