LOJ 2255 [SNOI 2017] 炸弹

简化了的线段树优化建图

思路:

一个炸弹炸的范围是一个区间,考虑线段树优化建图.

这道题是一个点向一个区间连边,就只需要建一棵线段树了.

建一棵线段树,从上向下连节点.当我们需要用炸弹向爆炸区间连边时,我们从它所对应的线段树叶子节点向线段树的区间连边

对于可以互相炸到的炸弹,我们可以跑一边Tarjan缩个点,方便统计.

统计理论上应该用拓扑,但我脑抽了写了个dfs(


代码:

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
#include <bits/stdc++.h>
#define ll long long

const int N = 5002333, MO = 1000000007;
struct Edge {int to, nxt;} e[N << 3], c[N << 3];
struct SegTree {
int l, r, ls, rs;
} t[N << 2];
int head[N], ecnt, ccnt, hc[N], tot, pos[N], n, root, f[N], ans, vis[N], tim, cnt;
ll x[N], r[N];

void AddEdge(int f, int to) {
e[++ecnt] = {to, head[f]}, head[f] = ecnt;
}

void AddC(int f, int to) {
c[++ccnt] = {to, hc[f]}, hc[f] = ccnt;
}

void Build(int &p, int l, int r) {
p = ++tot, t[p].l = l, t[p].r = r;
if (l == r) {pos[l] = p; return;}
int mid = (l + r) >> 1;
Build(t[p].ls, l, mid), Build(t[p].rs, mid + 1, r);
AddEdge(p, t[p].ls), AddEdge(p, t[p].rs);
}

void Link(int p, int l, int r, int v) {
if (t[p].l >= l && t[p].r <= r) {
if (pos[v] == p) return;
AddEdge(pos[v], p); return;
}
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) Link(t[p].ls, l, r, v);
if (r > mid) Link(t[p].rs, l, r, v);
}

int dfn[N], low[N], stk[N], id[N], siz[N], p, num, scc;
bool ins[N];

void Tarjan(int x) {
dfn[x] = low[x] = ++num;
stk[++p] = x, ins[x] = 1;
for (int i = head[x], y = e[i].to; i; i = e[i].nxt, y = e[i].to) {
if (!dfn[y]) {
Tarjan(y), low[x] = std::min(low[x], low[y]);
} else if (ins[y]) low[x] = std::min(low[x], dfn[y]);
}
if (low[x] == dfn[x]) {
++scc; int z;
do {
z = stk[p--], ins[z] = 0, id[z] = scc;
} while (x != z);
}
}

void dfs(int x) {
vis[x] = tim, cnt += siz[x];
for (int i = hc[x], y = c[i].to; i; i = c[i].nxt, y = c[i].to)
if (vis[y] != tim)
vis[y] = tim, dfs(y);
}

int Solve(int x) {
x = id[pos[x]];
if (f[x]) return f[x];
tim++, cnt = 0;
dfs(x);
return f[x] = cnt;
}

signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &x[i], &r[i]);
Build(root, 1, n);
for (int i = 1; i <= n; i++) {
int L = std::lower_bound(x + 1, x + 1 + n, x[i] - r[i]) - x;
int R = std::upper_bound(x + 1, x + 1 + n, x[i] + r[i]) - x - 1;
Link(1, L, R, i);
}
for (int i = 1; i <= n; i++)
if (!dfn[pos[i]]) Tarjan(pos[i]);
for (int x = 1; x <= tot; x++)
for (int i = head[x], y = e[i].to; i; i = e[i].nxt, y = e[i].to)
if (id[x] != id[y]) AddC(id[x], id[y]);
for (int i = 1; i <= n; i++) siz[id[pos[i]]]++;
for (int i = 1; i <= n; i++)
(ans += (long long) i * (long long) Solve(i) % MO) %= MO;
return !printf("%d\n", ans);
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×