Description
在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi，爆炸半径是 Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置 Xj 满足：
Xi−Ri≤Xj≤Xi+Ri,那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 i 个炸弹引爆，将引爆多少个炸弹呢？
Input
第一行，一个数字 N，表示炸弹个数。
第 2∼N+1行，每行 2 个数字，表示 Xi，Ri，保证 Xi 严格递增。
N≤500000
−10^18≤Xi≤10^18
0≤Ri≤2×10^18
Output
一个数字，表示Sigma(i*炸弹i能引爆的炸弹个数),1<=i<=N mod10^9+7。
题解
因为每一个炸弹爆炸后引爆的是一个区间的炸弹，所以想到线段树优化建图。
然后可能有环所以跑Tarjan求强连通分量。最后拓扑合并答案。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=;
const int mod=1e9+;
queue<int> q;
int cnt,cnt1,head[N*],head1[N*];
int num,id[N*],di[N*];
int dfn[N*],low[N*],tot1,top,stack[N*],book[N*],num1,col[N*],tmp;
long long a[N],r[N],b[N],maxx[N*],minn[N*];
int n,tot,in[N*];
long long ans;
struct tree{
int l,r;
}tr[N*];
struct edge{
int to,nxt,u;
}e[N*],e1[N*];
void add(int u,int v){
cnt++;
e[cnt].nxt=head[u];
e[cnt].u=u;
e[cnt].to=v;
head[u]=cnt;
}
void add1(int u,int v){
cnt1++;
e1[cnt1].nxt=head1[u];
e1[cnt1].to=v;
head1[u]=cnt1;
}
void build(int l,int r,int now){
num=max(num,now);
tr[now].l=l;tr[now].r=r;
if(r==l){
id[l]=now;
di[now]=l;
return;
}
int mid=(tr[now].l+tr[now].r)>>;
build(l,mid,now*);
build(mid+,r,now*+);
add(now,now*);
add(now,now*+);
}
void update(int l,int r,int now,int u){
if(tr[now].l==l&&tr[now].r==r){
add(u,now);
return;
}
int mid=(tr[now].l+tr[now].r)>>;
if(l>mid)update(l,r,now*+,u);
else if(r<=mid)update(l,r,now*,u);
else{
update(l,mid,now*,u);
update(mid+,r,now*+,u);
}
}
void Tarjan(int u){
dfn[u]=low[u]=++tot1;
stack[++top]=u;
book[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dfn[v]==){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(book[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int x;
num1++;
minn[num1]=4e18;
maxx[num1]=-4e18;
bool flag=false;
do{
x=stack[top--];
book[x]=;
col[x]=num1;
if(di[x]){
if(!flag){
minn[num1]=a[di[x]]-r[di[x]];
maxx[num1]=a[di[x]]+r[di[x]];
flag=true;
}
else{
minn[num1]=min(minn[num1],a[di[x]]-r[di[x]]);
maxx[num1]=max(maxx[num1],a[di[x]]+r[di[x]]);
}
}
}while(x!=u);
}
}
int lower(long long x){
int ll=;int rr=tot+;
while(ll<=rr){
int mid=(ll+rr)>>;
if(b[mid]>=x){
tmp=mid;
rr=mid-;
}
else ll=mid+;
}
return tmp;
}
int uppr(long long x){
int ll=;int rr=tot+;
while(ll<=rr){
int mid=(ll+rr)>>;
if(b[mid]>x){
tmp=mid;
rr=mid-;
}
else ll=mid+;
}
return tmp;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lld%lld",&a[i],&r[i]);
b[i]=a[i];
}
tot=unique(b+,b++n)-(b+);
b[tot+]=4e18;
build(,n,);
for(int i=;i<=n;i++){
int x=lower(a[i]-r[i]);
int y=uppr(a[i]+r[i])-;
update(x,y,,id[i]);
}
for(int i=;i<=num;i++){
if(!dfn[i])Tarjan(i);
}
for(int i=;i<=cnt;i++){
if(col[e[i].u]==col[e[i].to])continue;
add1(col[e[i].to],col[e[i].u]);
in[col[e[i].u]]++;
}
for(int i=;i<=num1;i++){
if(in[i]==)q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head1[u];i;i=e1[i].nxt){
int v=e1[i].to;
in[v]--;
if(in[v]==)q.push(v);
minn[v]=min(minn[v],minn[u]);
maxx[v]=max(maxx[v],maxx[u]);
}
}
for(int i=;i<=n;i++){
int x=uppr(maxx[col[id[i]]])-;
int y=lower(minn[col[id[i]]]);
ans+=(long long)((long long)(x-y+)*(long long)i)%mod;
ans%=mod;
}
printf("%lld",ans);
return ;
}