Loj 2255 炸弹

Posted on | Views:

tarjan 求 SCC.

若 $i$ 能炸到 $j$ ,就从 $i$ 向 $j$ 连一条边,那么 $i$ 的答案就是从 $i$ 出发能到的点的数目

直接做传递闭包的时间复杂度为 $O(\frac{n^3}{w})$ .

注意到一个点能炸到的点一定是一段连续区间,可以用 $l_i,r_i$ 表示.

用 tarjan 求出每个 SCC,缩点之后变成一张 DAG, 在 DAG 上按照拓扑序逆序 dp 更新 $l,r$ 即可.

如果直接暴力连边,边数是 $O(n^2)$ 的,可以用线段树优化到 $O(n\log n)$ .

进一步优化,注意到对于炸弹 $i$ ,从左边连向它的边中,只需要保留距离它最近的点连来的边,右边也是一样.

因为更左边的点若能炸到 $i$ ,那么也一定能炸到左边最近能炸到 $i​$ 的点,就可以传递过来了.

时间复杂度 $O(n)$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 5e5 + 10;
int n, stk[N], tp = 0, lb[N], rb[N], dfn[N], low[N], in[N], bel[N];
int idx = 0, tot = 0;
ll X[N], R[N];
vector<int> G[N], scc_G[N];
void tarjan(int u)
{
	dfn[u] = low[u] = ++idx;
	stk[++tp] = u, in[u] = 1;
	for (int v : G[u])
	{
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u])
	{
		++tot;
		int x = 0;
		while (x != u)
		{
			x = stk[tp--];
			bel[x] = tot;
			lb[tot] = min(lb[tot], x), rb[tot] = max(rb[tot], x);
			in[x] = 0;
		}
	}
}
int vis[N];
void calc(int x)
{
	vis[x] = 1;
	for (int y : scc_G[x])
	{
		if (!vis[y])
			calc(y);
		lb[x] = min(lb[x], lb[y]);
		rb[x] = max(rb[x], rb[y]);
	}
}
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
		X[i] = read(), R[i] = read();
	tp = 0;
	for (int i = 1; i <= n; ++i)
	{
		while (tp && X[stk[tp]] + R[stk[tp]] < X[i])
			--tp;
		if (tp)
			G[stk[tp]].push_back(i);
		while (tp && X[stk[tp]] + R[stk[tp]] <= X[i] + R[i])
			--tp;
		stk[++tp] = i;
	}
	tp = 0;
	for (int i = n; i >= 1; --i)
	{
		while (tp && X[stk[tp]] - R[stk[tp]] > X[i])
			--tp;
		if (tp)
			G[stk[tp]].push_back(i);
		while (tp && X[stk[tp]] - R[stk[tp]] >= X[i] - R[i])
			--tp;
		stk[++tp] = i;
	}
	for (int i = 1; i <= n; ++i)
		lb[i] = n + 1, rb[i] = 0;
	tp = 0;
	for (int i = 1; i <= n; ++i)
		if (!dfn[i])
			tarjan(i);
	for (int i = 1; i <= n; ++i)
		for (int j : G[i])
			scc_G[bel[i]].push_back(bel[j]);
	for (int i = 1; i <= tot; ++i)
		if (!vis[i])
			calc(i);
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		inc(ans, mul(i, rb[bel[i]] - lb[bel[i]] + 1));
	write(ans, '\n');
	return 0;
}