方法一：
朴素思路：果断建图，每次二分出一个区间然后要向这个区间每个点连有向边，然后一个环的话是可以互相引爆的，缩点之后就是一个DAG，求每个点出发有多少可达点。
然后注意两个问题：
- 上述建边显然$n^2$爆炸。因为是区间建边，所以用线段树建边优化，不过这题比较特殊，只是点向区间连边，分析线段树建边原理，可以完全把出树省掉，就用一个入树连边就行了。（其实边数还是很多，所以边上界我开了$2\times 10^7$。。。）
- 这样缩点后DAG上找连通点数，有一道类似的题，不过最多数据只能出到$2000$，但是这题$n$是在$5e5$级别的，所以应当是和区间的特殊性质有一些关联的。`````发现每个炸弹引爆之后，向左向右引爆到的炸弹序号都必然是连续的一段。。所以只要对DAG上每个点可达的最大最小编号算一下就行了。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define mst(x) memset(x,0,sizeof x)
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=5e5+,P=1e9+;
int n,cnt,ans;
struct thxorz{
int head[N<<],nxt[N*],to[N*],tot;
inline void add(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
}G1,G2;
struct SGT{
int id[N<<];
#define lc i<<1
#define rc i<<1|1
inline void build(int i,int L,int R){
if(L==R){id[i]=L;return;}
int mid=L+R>>;id[i]=++cnt;
build(lc,L,mid),build(rc,mid+,R);
G1.add(id[i],id[lc]),G1.add(id[i],id[rc]);
}
inline void update(int i,int L,int R,int ql,int qr,int x){
if(ql<=L&&qr>=R){G1.add(x,id[i]);return;}
int mid=L+R>>;
if(ql<=mid)update(lc,L,mid,ql,qr,x);
if(qr>mid)update(rc,mid+,R,ql,qr,x);
}
}T;
ll pos[N],r[N];
int dfn[N<<],low[N<<],stk[N<<],instk[N<<],bel[N<<],minv[N<<],maxv[N<<],vis[N<<],scc,top,tim;
#define y G1.to[j]
void tarjan(int x){
dfn[x]=low[x]=++tim,stk[++top]=x,instk[x]=;
for(register int j=G1.head[x];j;j=G1.nxt[j]){
if(!dfn[y])tarjan(y),MIN(low[x],low[y]);
else if(instk[y])MIN(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
int tmp;++scc;
do{
instk[tmp=stk[top--]]=,bel[tmp]=scc;
if(tmp<=n)MIN(minv[scc],tmp),MAX(maxv[scc],tmp);
}while(tmp^x);
}
}
#undef y
#define y G2.to[j]
void dp(int x){
if(vis[x])return;
vis[x]=;
for(register int j=G2.head[x];j;j=G2.nxt[j])dp(y),MIN(minv[x],minv[y]),MAX(maxv[x],maxv[y]);
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
cnt=read(n);memset(minv,0x3f,sizeof minv);
for(register int i=;i<=n;++i)read(pos[i]),read(r[i]);
T.build(,,n);
for(register int i=;i<=n;++i){
int lb=lower_bound(pos+,pos+n+,pos[i]-r[i])-pos;
int rb=upper_bound(pos+,pos+n+,pos[i]+r[i])-pos-;
T.update(,,n,lb,rb,i);
}
for(register int i=;i<=cnt;++i)if(!dfn[i])tarjan(i);
#define y G1.to[j]
for(register int i=;i<=cnt;++i){
for(register int j=G1.head[i];j;j=G1.nxt[j])
if(bel[i]^bel[y])G2.add(bel[i],bel[y]);
}
#undef y
for(register int i=;i<=n;++i)dp(bel[i]),ans=(ans+i*1ll*(maxv[bel[i]]-minv[bel[i]]+))%P;
printf("%d\n",ans);
return ;
}
然后发现这种做法超级繁诶，对比一下榜rk1，时间，尤其是空间都很逊。。所以学习了一下原题正解。
方法二：神仙递推
首先对于每个炸弹，计算他最终能引爆的左边界和右边界。初始时，$lb_i=rb_i=i$。
分析情况，会发现，有这几种引爆方式：
- 一直沿着左边炸
- 一直沿着右边炸
- 先炸了左边，左边的触发了右边原本触发不了的（然后可能右边那个再触发更左边的，如此往复。。。）
- 先炸了右边，然后。。。同上一个
对于前两种，直接正一边反一遍推就行了。但是第三四种的话，需要从左至右对每个炸弹$i$先处理一下只考虑引爆左侧炸弹能拓展到的最远可达点$lb$，并且维护出一个这些可达引爆点中向右可达范围最远的距离表示$i$的新半径。然后，再从右向左推，对于每个点$i$，利用新半径去触发右侧点，并且用这些右侧点的$lb$和$rb$来更新自己。由于右边的边界处答案肯定是对的，向左的时候，只要把右边上一次的$lb$和$rb$合并过来，就可以求得这个点的$lb$和$rb$。
是不是超有道理的。。
具体还是看code。。不过我一开始因为不太理解思路，看了一个本来就写错了的老哥的题解，自己也写错了，成功被loj数据hack掉了，后来想了好长时间自己改了一下才过的。。大致是每次在拓展左边界时候更新半径，然后引爆右侧时候更新自己的答案。注意一下更新顺序，我就是这里被hack的。
因为还不是特别理解，所以可能code还有问题，所以，欢迎hack。
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i(a);i<=b;++i)
#define per(i,a,b) for(register int i(a);i>=b;--i)
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=5e5+,P=1e9+;
ll x[N],r[N];
int lb[N],rb[N],n,ans; int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
read(n);rep(i,,n)read(x[i]),read(r[i]),lb[i]=rb[i]=i;
rep(i,,n)while(lb[i]>&&x[i]-x[lb[i]-]<=r[i])MAX(r[i],r[lb[i]-]-(x[i]-x[lb[i]-])),lb[i]=lb[lb[i]-];
per(i,n,)while(rb[i]<n&&x[rb[i]+]-x[i]<=r[i])MIN(lb[i],lb[rb[i]+]),rb[i]=rb[rb[i]+];
rep(i,,n)ans=(ans+i*1ll*(rb[i]-lb[i]+))%P;
return printf("%d\n",ans);
}
忘说一件事。。上述做法是线性的，因为每次向左更新可达点，如果某次半径内有多个断开的块的时候，会把他们合并起来，这样所有块只会被合并一次。所以是线性的。