「BZOJ5017」[Snoi2017]炸弹

Description

在一条直线上有 NN 个炸弹,每个炸弹的坐标是 XiX_i,爆炸半径是 RiR_i,当一个炸弹爆炸时,如果另一个炸弹所在位置 XjX_j 满足:

XiRiXjXi+RiX_i-R_i\leq X_j \leq X_i+R_i

那么,该炸弹也会被引爆。

现在,请你帮忙计算一下,先把第 ii 个炸弹引爆,将引爆多少个炸弹呢?

Input

第一行,一个数字 NN,表示炸弹个数。
2N+12\sim N+1 行,每行 22 个数字,表示 XiX_iRiR_i,保证 XiX_i 严格递增。

Output

一个数字,表示 $\sum \limits_{i=1}^n i\times $ 炸弹 ii 能引爆的炸弹个数 mod109+7\mod 10^9+7

Sample Input

1
2
3
4
5
4
1 1
5 1
6 5
15 15

Sample Output

1
32

HINT

20%20\% 的数据:N100N\leq 100
50%50\% 的数据:N1000N\leq 1000
80%80\% 的数据:N100000N\leq 100000
100%100\% 的数据:N500000N\leq 5000001018Xi1018-10^{18}\leq X_i\leq 10^{18}0Ri2×10180\leq R_i\leq 2\times 10^{18}

Solution

对于每一个炸弹找到[L,R][L,R],然后线段树优化建边。
建边之后tarjan缩点,但是DAG要求自己可以到的最小编号和最大编号,然后答案就是rili+1r_i-l_i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 510000 * 4, M = 510000 * 4;
int n;
int cnt;
int mn[N], mx[N];
struct Grap {
struct Edge {
int v, nxt;
}e[M * 8];
int head[N], en, d[N];
void addedge(int x, int y) {
e[en].v = y, e[en].nxt = head[x], head[x] = en;
++d[y];
}
void solve() {
queue<int>q;
for(int i = 1; i <= cnt; ++i) if(!d[i]) q.push(i);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
mn[y] = min(mn[y], mn[x]);
mx[y] = max(mx[y], mx[x]);
if(!--d[y]) q.push(y);
}
}
}
}g;
struct Edge {
int u, v, nxt;
bool w;
}e[M * 8];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
}
struct Tree {
int l, r;
}t[N];
int rt, tot;
void build(int &o, int l, int r) {
o = ++tot;
if(l == r) {
addedge(o, l, 0);
return;
}
int mid = (l + r) >> 1;
if(l <= mid) {
build(t[o].l, l, mid);
addedge(o, t[o].l, 0);
}
if(r > mid) {
build(t[o].r, mid + 1, r);
addedge(o, t[o].r, 0);
}
}
struct Point {
ll x, r;
}a[N / 4];
int findl(ll x) {
int l = 0, r = n;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(a[mid].x >= x) r = mid;
else l = mid;
}
return r;
}
int findr(ll x) {
int l = 1, r = n + 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(a[mid].x <= x) l = mid;
else r = mid;
}
return l;
}
void ins(int o, int L, int R, int l, int r, int x) {
if(l <= L && r >= R) {
addedge(x, o, 1);
return;
}
int mid = (L + R) >> 1;
if(l <= mid) ins(t[o].l, L, mid, l, r, x);
if(r > mid) ins(t[o].r, mid + 1, R, l, r, x);
}
int st[N], top, dfn[N], low[N], num, scc[N];
bool vis[N];
void tarjan(int x) {
st[++top] = x;
dfn[x] = low[x] = ++num;
vis[x] = 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;

if(!dfn[y]) {
tarjan(y);
low[x] = min(low[y], low[x]);
} else if(vis[y]) low[x] = min(low[x], dfn[y]);
}
if(dfn[x] == low[x]) {
int y; ++cnt;
mn[cnt] = 1e9;
mx[cnt] = -1e9;
do {
y = st[top--];
vis[y] = 0;
scc[y] = cnt;
if(y <= n)mx[cnt] = max(mx[cnt], y);
if(y <= n)mn[cnt] = min(mn[cnt], y);
}while(x != y);
}
}
int main() {
n = read();
tot = n;
build(rt, 1, n);
for(int i = 1; i <= n; ++i) {
a[i].x = read();
a[i].r = read();
}
for(int i = 1; i <= n; ++i) {
int L = findl(a[i].x - a[i].r);
int R = findr(a[i].x + a[i].r);
ins(rt, 1, n, L, R, i);
}
for(int i = 1; i <= tot; ++i)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= en; ++i)
if(scc[e[i].u] != scc[e[i].v]) g.addedge(scc[e[i].v],scc[e[i].u]);
g.solve();
const ll p = 1e9 + 7;
ll ans = 0;
for(int i = 1; i <= n; ++i) {
ans += (ll)i * (mx[scc[i]] - mn[scc[i]] + 1);
ans %= p;
}
writeln(ans);
return 0;
}