[学习笔记]线段树优化建图

时间:2022-12-31 14:12:05

一个点向一个点连边太easy了。

现实有的时候并没有这么简单。

 

对于这样的一类问题:
需要多次(m=1e5次左右)从一个编号在[L1,R1]的区间内的所有点,向另一个编号在[L2,R2]的所有点之间分别连权值相同的边。

求S到T的最短路,或者其他的信息。

就是一个建图的辅助工具。解题具体思想还是靠图论。

 

暴力连边是O(mn^2)的。时空不足。

对于区间连边,我们考虑处理区间问题的大杀器:线段树。

具体做法如下:

建造两棵线段树A,B

A保存入的信息,B保存出的信息。

到了A的某个节点,代表进入了这个点所代表的区间,位置可以认为是区间所有的包含点的叠加态。

到了B的某个节点,代表可以从这个点代表的区间中的任意一个边出去。

连边:

1.A树父亲向儿子连0边,能够进入父亲节点,必然就可以选择进入儿子节点。叠加态具体化。

2.B树儿子向父亲连0边,儿子属于父亲节点,父亲节点代表区间连出去边,儿子节点也一定可以走。

3.A树B树间的平行节点之间,由A向B连0边,代表,我进入A点,必然可以选择从A点出去。

4.对于题目要求加入的边(真边),建立虚拟节点P,在B中把出区间拆成logn份,分别连接到P点,边权为0

  在A中把入区间拆成logn份,点P分别连接到这些区间,边权都是val

  (当然,边权可以反过来)

然后跑最短路即可。

边数:O(2*2*n+m*logn*2)

点数:O(2*2*n+m)

 

模板题:CF786D

 

当然,也要解决一些其他抽象的问题:

 

[POI2015]PUS

 

以及炸弹:

bzoj 5017 炸弹 线段树优化建图+tarjan+拓扑排序