终于搞出来了,三代目的时候说再重构就吃屏幕,但是不调出来真的害怕(不知道自己哪里错了,万一考试的时候被搞了就完了)
不能发题解,就发个讨论,提醒一下各位做这道题目的。
这道题目可以在 Tarjan 的时候同时算出答案来,Tarjan 找到一个环时,更新环上的所有答案,其余情况正常转移。
其他地方都 A 了,但是 luogu 的数据真的强,有一个地方是出锅了的,可以去看看我前面的代码。
重点:Tarjan 的同时计算答案,需要考虑兄弟边的影响。
平时写 Tarjan 写惯了,只考虑出边和反祖边,兄弟边都是直接忽略的,而这里兄弟边也会对答案产生影响。
就这样了,我来吃屏幕了。
/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;
typedef long long readtype;
typedef long long var;
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 = 5e5 + 1;
const int M = 2e7 + 1;
const int MOD = 1e9 + 7;
inline int add(int a, int b) { return (a + b >= MOD) ? (a + b - MOD) : (a + b); }
inline int mul(var a, int b) { return (a * b) % MOD; }
int n, id[N];
var x[N], r[N];
int lpos[M], rpos[M];
int top, fi[M], ne[M << 1], to[M << 1];
int T, dfn[M], low[M];
int cnt, sta[M];
bool insta[M];
void Add(int u, int v);
void Build(int t, int l, int r);
void Modify(int x, int y, int v, int t, int l, int r);
void Tarjan(int t);
int main() {
n = read();
for (int i = 1; i <= n; ++i)
x[i] = read(), r[i] = read();
Build(1, 1, n);
for (int i = 1; i <= n; ++i) {
int lx = lower_bound(x + 1, x + n + 1, x[i] - r[i]) - x;
int rx = upper_bound(x + 1, x + n + 1, x[i] + r[i]) - x - 1;
Modify(lx, rx, id[i], 1, 1, n);
}
Tarjan(1);
int res = 0;
for (int i = 1; i <= n; ++i)
res = add(res, mul(i, rpos[id[i]] - lpos[id[i]] + 1));
printf("%d\n", res);
return 0;
}
void Add(int u, int v) {
ne[++top] = fi[u], fi[u] = top, to[top] = v;
}
void Build(int t, int l, int r) {
lpos[t] = l, rpos[t] = r;
int mid = (l + r) >> 1;
if (l == r) {
id[mid] = t;
return ;
}
Build(t << 1, l, mid), Build(t << 1 | 1, mid + 1, r);
Add(t, t << 1), Add(t, t << 1 | 1);
}
void Modify(int x, int y, int v, int t, int l, int r) {
if (x <= l && r <= y) {
if (v != t) Add(v, t);
return ;
}
int mid = (l + r) >> 1;
if (x <= mid) Modify(x, y, v, t << 1, l, mid);
if (y > mid) Modify(x, y, v, t << 1 | 1, mid + 1, r);
}
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]]);
lpos[t] = min(lpos[t], lpos[to[i]]);
rpos[t] = max(rpos[t], rpos[to[i]]);
}
else if (insta[to[i]]) low[t] = min(low[t], dfn[to[i]]);
else {
lpos[t] = min(lpos[t], lpos[to[i]]);
rpos[t] = max(rpos[t], rpos[to[i]]);
}
}
if (dfn[t] == low[t]) {
int tlpos = lpos[t], trpos = rpos[t];
for (int i = cnt; sta[i + 1] != t; --i) {
tlpos = min(tlpos, lpos[sta[i]]);
trpos = max(trpos, rpos[sta[i]]);
}
for (int i = cnt; sta[i + 1] != t; --i)
lpos[sta[i]] = tlpos, rpos[sta[i]] = trpos;
while (sta[cnt + 1] != t) {
int x = sta[cnt--];
insta[x] = false;
}
}
}