有大佬指出开 O2 以后多过了两个点,疑似 UB,调试不能,继续求助。
代码风格已修正。
typedef long long readtype;
/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;
typedef long long var;
typedef long double let;
readtype read() {
readtype a = 0, c = getchar(), s = 0;
while (!isdigit(c)) s |= c == '-', c = getchar();
while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
return s ? -a : a;
}
/* }}} */
const int N = 4e6 + 1;
const int M = 4e6 + 1;
const int MOD = 1e9 + 7;
struct Line {
int u, v;
};
int n;
var x[N], r[N];
int node_able_l[N], node_able_r[N];
int m;
Line line[M];
int tree_node_num, root, lson[N << 2], rson[N << 2];
int tree_id[N], tree_able_l[N], tree_able_r[N];
int top, fi[N], ne[M << 1], to[M << 1];
int tot, col[N], size[N];
int cir_able_l[N], cir_able_r[N];
int T, dfn[N], low[N];
int cnt, sta[N];
bool insta[N];
void Build(int &t, int l = 1, int r = n);
void Modify(int x, int y, int id, int t = root, int l = 1, int r = n);
void Add(int u, int v);
void Tarjan(int t);
int main() {
n = read();
for (int i = 1; i <= n; ++i) x[i] = read(), r[i] = read();
for (int i = 1; i <= n; ++i) {
node_able_l[i] = lower_bound(x + 1, x + n + 1, x[i] - r[i]) - x;
node_able_r[i] = upper_bound(x + 1, x + n + 1, x[i] + r[i]) - x - 1;
}
Build(root);
for (int i = 1; i <= n; ++i)
Modify(node_able_l[i], node_able_r[i], tree_id[i]);
for (int i = 1; i <= n; ++i)
if (!dfn[tree_id[i]]) Tarjan(tree_id[i]);
var res = 0;
for (int i = 1; i <= n; ++i) {
var able_num = cir_able_r[col[tree_id[i]]] - cir_able_l[col[tree_id[i]]] + 1;
(res += (able_num * i) % MOD) %= MOD;
}
printf("%lld\n", res);
return 0;
}
void Build(int &t, int l, int r) {
t = ++tree_node_num;
int mid = (l + r) >> 1;
if (l == r) {
tree_id[mid] = t;
tree_able_l[t] = node_able_l[mid];
tree_able_r[t] = node_able_r[mid];
return ;
}
tree_able_l[t] = n, tree_able_r[t] = 1;
Build(lson[t], l, mid), Build(rson[t], mid + 1, r);
Add(t, lson[t]), Add(t, rson[t]);
line[++m] = (Line) {t, lson[t]}, line[++m] = (Line) {t, rson[t]};
}
void Modify(int x, int y, int tree_id, int t, int l, int r) {
if (x > r || y < l) return ;
if (x <= l && r <= y) {
Add(tree_id, t);
line[++m] = (Line) {tree_id, t};
return ;
}
int mid = (l + r) >> 1;
Modify(x, y, tree_id, lson[t], l, mid);
Modify(x, y, tree_id, rson[t], mid + 1, r);
}
void Add(int u, int v) {
ne[++top] = fi[u], fi[u] = top, to[top] = v;
}
void Tarjan(int t) {
dfn[t] = low[t] = ++T;
sta[++cnt] = t;
insta[t] = true;
for (int i = fi[t]; i; i = ne[i]) {
if (!dfn[to[i]]) {
Tarjan(to[i]), low[t] = min(low[t], low[to[i]]);
tree_able_l[t] = min(tree_able_l[t], tree_able_l[to[i]]);
tree_able_r[t] = max(tree_able_r[t], tree_able_r[to[i]]);
}
else if (insta[to[i]]) low[t] = min(low[t], dfn[to[i]]);
}
if (dfn[t] == low[t]) {
tot++;
cir_able_l[tot] = n, cir_able_r[tot] = 1;
while (sta[cnt + 1] != t) {
int x = sta[cnt--];
insta[x] = false, col[x] = tot;
cir_able_l[tot] = min(cir_able_l[tot], tree_able_l[x]);
cir_able_r[tot] = max(cir_able_r[tot], tree_able_r[x]);
}
}
}