摘要:线段树建图后跑tarjan

「SNOI2017」炸弹

题面

题目分析

图论的模型应该很好建出来,对爆炸后能够波及到的炸弹连边,那么选定一个炸弹进行爆炸能够引爆的总个数即为强联通分量的大小,用tarjan跑一下即可.

但是这个值域太大了无法直接建图,考虑使用线段树来建图,也就是一个点连向线段树上的节点.

显然线段树是建在点集上,父亲向两个儿子连边,还要记录一下原序列上的点对应树上的节点.

二分求出每个炸弹爆炸后最左最右能够波及到的点,然后将序列上的点对应在树上的点向这个区间连边,就是向线段树上将大区间拆分出来的几个代表小区间的树上节点连边.

然后用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
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
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 4557430888798830399
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef int lxl;
const lxl big=500010,mod=1000000007;
lxl n,m,NodeCnt,TimeCnt,root,SccCnt,ans;
lxl c[2][big<<2],dfn[big<<2],scc[big<<2],low[big<<2],left[big<<2],right[big<<2],head[big<<2],vis[big<<2],id[big];
long long x[big],r[big];
struct _Node
{
lxl l,r;
}a[big<<2];
std::vector<lxl>map[big<<2],e[big<<2];
std::stack<lxl>s;
inline lxl read()
{
char c(getchar());
long long f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void EdgeAdd(lxl u,lxl v)
{
e[u].push_back(v);
}
void add(lxl t,lxl l,lxl r,lxl x,lxl y,lxl u)
{
if(x<=l&&y>=r)
{
if(u!=t)EdgeAdd(u,t);
return;
}
lxl mid((l+r)>>1);
if(x<=mid)add(c[0][t],l,mid,x,y,u);
if(y>mid)add(c[1][t],mid+1,r,x,y,u);
}
void BuildTree(lxl &t,lxl l,lxl r)
{
if(!t)t=++NodeCnt;
a[t].l=l,a[t].r=r;
if(l==r){id[l]=t;return;}
lxl mid((l+r)>>1);
BuildTree(c[0][t],l,mid),BuildTree(c[1][t],mid+1,r);
EdgeAdd(t,c[0][t]),EdgeAdd(t,c[1][t]);
}
void tarjan(lxl u)
{
dfn[u]=low[u]=++TimeCnt;
s.push(u),vis[u]=true;
for(auto it=e[u].begin();it!=e[u].end();++it)
{
lxl v=*it;
if(!dfn[v])tarjan(v),low[u]=std::min(low[u],low[v]);
else if(vis[v])low[u]=std::min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++SccCnt;
while(!s.empty())
{
lxl ki43=s.top();s.pop();
scc[ki43]=SccCnt,vis[ki43]=false;
left[SccCnt]=std::min(left[SccCnt],a[ki43].l);
right[SccCnt]=std::max(right[SccCnt],a[ki43].r);
if(ki43==u)break;
}
}
}
void dfs(lxl u)
{
vis[u]=true;
for(auto it=map[u].begin();it!=map[u].end();++it)
{
lxl v=*it;
if(vis[v])
{
left[u]=std::min(left[u],left[v]);
right[u]=std::max(right[u],right[v]);
continue;
}
dfs(v);
left[u]=std::min(left[u],left[v]);
right[u]=std::max(right[u],right[v]);
}
}
inline lxl query(lxl i){return right[scc[id[i]]]-left[scc[id[i]]]+1;}
int main(void)
{
memset(head,-1,sizeof head),memset(left,0x3f,sizeof left);
n=read();
for(R int i(1);i<=n;++i)scanf("%lld %lld",x+i,r+i);
x[n+1]=INF;
BuildTree(root,1,n);
for(R int i(1);i<=n;++i)
{
if(!r[i])continue;
lxl l_=std::lower_bound(x+1,x+1+n,x[i]-r[i])-x;
lxl r_=std::upper_bound(x+1,x+1+n,x[i]+r[i])-x-1;
add(root,1,n,l_,r_,id[i]);
a[id[i]].l=l_,a[id[i]].r=r_;
}
tarjan(1);
for(R int i(1);i<=NodeCnt;++i)
for(auto it=e[i].begin();it!=e[i].end();++it)
{
lxl v=*it;
if(scc[i]!=scc[v])map[scc[i]].push_back(scc[v]);
}
memset(vis,0,sizeof vis);
for(R int i(1);i<=SccCnt;++i)
{
std::sort(map[i].begin(),map[i].end());
std::unique(map[i].begin(),map[i].end());
}
for(R int i(1);i<=SccCnt;++i)if(!vis[i])dfs(i);
for(R int i(1);i<=n;++i)ans=(ans+(long long)query(i)*i%mod)%mod;
printf("%d\n",ans);
return 0;
}