Solution
一个点向一个区间内的所有点连边， 可以用线段树优化建图来优化 ： 前置技能传送门
然后就得到一个有向图， 一个联通块内的炸弹可以互相引爆， 所以进行缩点变成$DAG$
然后拓扑排序。 由于一次引爆的炸弹 一定是一个连续的区间内， 所以只需要记录左右边界， 并将左右边界转移给能到达它的联通块。
没写手工栈一直RE的我心里$mmp$啊。 为什么网上的题解都不写手工栈$QAQ$
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define ll long long
using namespace std; const int N = ;
const int mod = 1e9 + ;
const ll inf = 3e18; int n, lscnt;
int head[N], tot;
int Head[N], Tot;
int low[N], dfn[N], dfstot;
int c[N], col;
ll minn[N], maxn[N], ls[N];
int st[N], tp;
bool vis[N], inq[N]; struct edge {
int nxt, to;
}e[N * ], E[N * ]; struct boom {
ll pos, r;
}bo[N]; ll read() {
ll X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
} void Add(int u, int v) {
E[++Tot].to = v;
E[Tot].nxt = Head[u];
Head[u] = Tot;
} namespace SegT {
#define mid ((l + r) >> 1)
int lc[N], rc[N], root, cnt; void build(int &p, int l, int r) {
if (l == r) {
p = l; return;
}
p = ++cnt;
build(lc[p], l, mid);
build(rc[p], mid + , r);
add(p, lc[p]); add(p, rc[p]);
} void update(int L, int R, int c, int l, int r, int x) {
if (L > R) return;
if (L <= l && r <= R) {
add(c, x); return;
}
if (mid >= L)
update(L, R, c, l,mid, lc[x]);
if (mid < R)
update(L, R, c, mid + , r, rc[x]);
}
}using namespace SegT; #define R register
int stx[N], sti[N], lv, stnt[N];
#define u stx[lv]
#define nt stnt[lv]
#define i sti[lv]
void tarjan(int x) {
lv = ; stx[] = x;
start:;
low[u] = dfn[u] = ++dfstot;
inq[u] = true; st[++tp] = u;
for (i = head[u]; i; i = e[i].nxt) {
nt = e[i].to;
if (!dfn[nt]) {
// tarjan(nt);
stx[lv + ] = nt;
lv++;
goto start;
end:;
low[u] = min(low[u], low[nt]);
}
else if (inq[nt]) low[u] = min(low[u], dfn[nt]);
}
if (low[u] == dfn[u]) {
col++;
for (; tp;) {
int z = st[tp--];
inq[z] = false;
if (z <= n)
maxn[col] = max(maxn[col], bo[z].pos + bo[z].r),
minn[col] = min(minn[col], bo[z].pos - bo[z].r);
c[z] = col;
if (z == u) break;
}
}
--lv;
if (lv) goto end;
}
#undef u
#undef nt
#undef i void dfs(int u) {
vis[u] = true;
for (R int i = Head[u]; i; i = E[i].nxt) {
int nt = E[i].to;
if (vis[nt] == false) dfs(nt);
minn[u] = min(minn[u], minn[nt]);
maxn[u] = max(maxn[u], maxn[nt]);
}
} int fdl(ll x) {
return lower_bound(ls + , ls + + lscnt, x) - ls;
} int fdr(ll x) {
int re = lower_bound(ls + , ls + + lscnt, x) - ls;
if (ls[re] == x) return re;
else return re - ;
} int main()
{
cnt = n = rd;
for (R int i = ; i <= n; ++i) {
bo[i].pos = rd; bo[i].r = rd;
ls[++lscnt] = bo[i].pos;
}
sort(ls + , ls + + lscnt);
lscnt = unique(ls + , ls + + lscnt) - ls - ;
build(root, , n);
for (int i = ; i <= n; ++i) {
int l = fdl(bo[i].pos - bo[i].r), r = fdr(bo[i].pos + bo[i].r), m = fdl(bo[i].pos);
update(l, m - , m, , n, root);
update(m + , r, m, , n, root);
}
for (int i = ; i < N; ++i)
maxn[i] = -inf, minn[i] = inf;
for (int i = ; i <= cnt; ++i)
if (!dfn[i]) tarjan(i);
for (int u = ; u <= cnt; ++u)
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (c[u] == c[v])
continue;
Add(c[u], c[v]);
}
for (int i = ; i <= col; ++i) dfs(i);
ll ans = ;
for (int i = ; i <= n; ++i) {
int l = fdl(minn[c[i]]), r = fdr(maxn[c[i]]);
(ans += 1LL * i * (r - l + ) % mod) %= mod;
}
printf("%lld\n", ans);
}