题目链接
BZOJ：https://lydsy.com/JudgeOnline/problem.php?id=5017.
LOJ：https://loj.ac/problem/2255.
洛谷：https://www.luogu.org/problemnew/show/P5025.
Solution
这题有一个比较显然的暴力：
-
对于一个点(x)，我们二分出(l,r)表示(x)爆炸可以波及到的点的范围，然后我们从(x)向([l,r])分别连边。
-
建完图之后我们(tarjan)缩点，然后对于点(x)我们记录(L_x,R_x)表示(x)爆炸考虑连锁反应可以炸到的范围，这个在(DAG)上(dp)就可以了，这个点的答案就是(R_x-L_x+1)。
那么正解其实就很显然了，由于每次建边都是从一个点连向一个区间，那么直接线段树优化建图就好了。
具体的，我们建一棵(1sim n)的线段树，父亲向儿子连有向边，然后对于(x o [l,r])，我们把([l,r])拆成(O(log n))个区间，然后我们就只需要建(O(log n))条边了，然后缩点就直接在这个线段树上跑就好了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void read(ll &x) {
x=0;ll f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
#define lf double
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
const int maxn = 5e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int col,n,bel[maxn<<2],rev[maxn<<2];
struct Graph {
int head[maxn<<2],tot,deg[maxn<<2],l[maxn<<2],r[maxn<<2],t[maxn<<2],top;
struct edge{int to,nxt;}e[maxn<<3];
void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot,deg[v]++;}
void toposort() {
queue<int > q;
for(int i=1;i<=col;i++) if(!deg[i]) q.push(i);
while(!q.empty()) {
int now=q.front();q.pop();t[++top]=now;
for(int i=head[now];i;i=e[i].nxt)
if(!--deg[e[i].to]) q.push(e[i].to);
}
reverse(t+1,t+top+1);
for(int x=1;x<=top;x++) {
for(int i=head[x];i;i=e[i].nxt)
l[x]=min(l[x],l[e[i].to]),r[x]=max(r[x],r[e[i].to]);
}
}
void solve() {
int ans=0;
for(int i=1;i<=n;i++)
ans=(ans+1ll*i*(r[bel[rev[i]]]-l[bel[rev[i]]]+1)%mod)%mod;
write(ans);
}
}G;
ll pos[maxn],R[maxn];
int head[maxn<<2],tot,dfn[maxn<<2],low[maxn<<2],dfn_cnt,sta[maxn<<2],top,vis[maxn<<2],id[maxn<<2];
struct edge{int to,nxt;}e[maxn<<4];
void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
void build(int p,int l,int r) {
if(l==r) return rev[l]=p,id[p]=l,void();
ins(p,ls),ins(p,rs);
build(ls,l,mid),build(rs,mid+1,r);
}
void insert(int p,int l,int r,int x,int y,int t) {
if(x<=l&&r<=y) return ins(t,p),void();
if(x<=mid) insert(ls,l,mid,x,y,t);
if(y>mid) insert(rs,mid+1,r,x,y,t);
}
void tarjan(int x) {
dfn[x]=low[x]=++dfn_cnt,sta[++top]=x,vis[x]=1;
for(int v,i=head[x];i;i=e[i].nxt)
if(!dfn[v=e[i].to]) tarjan(v),low[x]=min(low[x],low[v]);
else if(vis[v]) low[x]=min(low[x],dfn[v]);
if(low[x]==dfn[x]) {
col++;int r;G.l[col]=1e9;
while(sta[top+1]!=x) {
bel[r=sta[top--]]=col,vis[r]=0;
if(id[r]) {
G.l[col]=min(G.l[col],id[r]);
G.r[col]=max(G.r[col],id[r]);
}
}
}
}
int main() {
scanf("%d",&n);build(1,1,n);
for(int i=1;i<=n;i++) read(pos[i]),read(R[i]);
for(int i=1;i<=n;i++) {
int l=lower_bound(pos+1,pos+n+1,pos[i]-R[i])-pos;
int r=upper_bound(pos+1,pos+n+1,pos[i]+R[i])-pos-1;
insert(1,1,n,l,r,rev[i]);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int x=1;x<=n;x++)
for(int i=head[x];i;i=e[i].nxt)
if(bel[e[i].to]!=bel[x]) G.ins(bel[x],bel[e[i].to]);
G.toposort(),G.solve();
return 0;
}