线段树优化建图
在某次CYjian神犇给我推了一道树剖+线段树优化建图+2-SAT的好(毒瘤)题后,发现自己竟然还 不会线段树优化建图，于是赶紧滚去学了一波，记下笔记
作用
用来解决区间连边(l,r)的每个点向(L,R)的每个点连边的建图方法。可以优化空间和时间。
实现
以CF786B为例。
题目要求支持以下三个操作:
单个点向单个点连边,权值为v
[
l
,
r
]
[l,r]
[l,r]中的每个点向单个点连边,权值为v
单个点向
[
l
,
r
]
[l,r]
[l,r]中的每个点连边,权值为v
然后求
s
s
s到每个点的单源最短路
考虑开两颗线段树，一颗用来维护2操作，一颗用来维护3操作。
对于2操作,如图:
]
考虑将线段树的每个节点也看做图中的一个点，同时每个点向父亲节点连一条权值为
0
0
0的边
接着做
2
2
2操作就可以在线段树中查找，当这个区间在线段树中被某个点包含后即用该点与单个点连边
即可，可以发现，区间
l
,
r
l,r
l,r中每个点都间接通过线段树中该点连向了要求的节点。
对于3操作，如图:
]
再造一颗线段树反过来连权值为
0
0
0的边，然后在按要求在线段树中连边即可。
最后从
s
s
s跑一遍
S
P
F
A
SPFA
SPFA(
S
P
F
A
S
SPFAS
SPFAS是不会死的！)即可。
代码
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std
;
struct IO
{
template<typename T
>
IO
& operator>>(T
&res
)
{
T q
=1;char ch
;
while((ch
=getchar())<'0' or ch
>'9')if(ch
=='-')q
=-q
;
res
=(ch
^48);
while((ch
=getchar())>='0' and ch
<='9') res
=(res
<<1)+(res
<<3)+(ch
^48);
res
*=q
;
return *this;
}
}cin
;
struct edge
{
int to
,next
,w
;
edge(int a
=0,int b
=0,int c
=0):to(a
),next(b
),w(c
){}
};
struct Node
{
int l
,r
;
Node(int x
=0,int y
=0):l(x
),r(y
){}
};
const int maxn
=1e5+10;
const int maxm
=3e5+10;
const long long inf
=9187201950435737471LL;
int head
[maxm
],cnt
,tot
,rtin
,rtout
,s
,n
,m
;
long long dis
[maxm
];
edge e
[maxn
*20];
Node tr
[maxm
];
void add(int u
,int v
,int w
)
{
e
[++cnt
]=edge(v
,head
[u
],w
);
head
[u
]=cnt
;
}
void buildin(int &k
,int l
,int r
)
{
if(l
==r
)
{
k
=l
;
return;
}
k
=++tot
;
int mid
=(l
+r
)>>1;
buildin(tr
[k
].l
,l
,mid
);
buildin(tr
[k
].r
,mid
+1,r
);
add(k
,tr
[k
].l
,0);
add(k
,tr
[k
].r
,0);
}
void buildout(int &k
,int l
,int r
)
{
if(l
==r
)
{
k
=l
;
return;
}
k
=++tot
;
int mid
=(l
+r
)>>1;
buildout(tr
[k
].l
,l
,mid
);
buildout(tr
[k
].r
,mid
+1,r
);
add(tr
[k
].l
,k
,0);
add(tr
[k
].r
,k
,0);
}
void update(int k
,int l
,int r
,const int &x
,const int &y
,
const int &u
,const int &w
,const int type
)
{
if(l
>=x
&& r
<=y
)
{
type
==2?add(u
,k
,w
):add(k
,u
,w
);
return;
}
if(l
>y
|| r
<x
)return;
int mid
=(l
+r
)>>1;
update(tr
[k
].l
,l
,mid
,x
,y
,u
,w
,type
);
update(tr
[k
].r
,mid
+1,r
,x
,y
,u
,w
,type
);
}
void SPFA(int s
)
{
memset(dis
,0x7f,sizeof dis
); dis
[s
]=0;
queue
<int>que
; que
.push(s
);
while(!que
.empty())
{
int u
=que
.front(); que
.pop();
for(int i
=head
[u
];i
;i
=e
[i
].next
)
if(dis
[e
[i
].to
]>dis
[u
]+e
[i
].w
)
dis
[e
[i
].to
]=dis
[u
]+e
[i
].w
,que
.push(e
[i
].to
);
}
}
int main()
{
cin
>>n
>>m
>>s
;
tot
=n
;
buildin(rtin
,1,n
);
buildout(rtout
,1,n
);
while(m
--)
{
int opt
,u
,v
,w
,x
,y
;
cin
>>opt
;
if(opt
==1)
{
cin
>>u
>>v
>>w
;
add(u
,v
,w
);
}
else
{
cin
>>u
>>x
>>y
>>w
;
update(opt
==2?rtin
:rtout
,1,n
,x
,y
,u
,w
,opt
);
}
}
SPFA(s
);
for(int i
=1;i
<=n
;i
++)
printf("%lld ",dis
[i
]==inf
?-1:dis
[i
]);
putchar('\n');
return 0;
}
