线段树优化建图

CF786Bcode

题意:单源最短路,连边有以下三种形式:

  • 1 u v w,连一条 $u\to v$,权值为 $w$ 的有向边。
  • 2 u l r w,$\forall v\in[l,r]$,连一条 $u\to v$,权值为 $w$ 的有向边。
  • 3 u l r w,$\forall v\in[l,r]$,连一条 $v\to u$,权值为 $w$ 的有向边。

由于线段树拆分区间复杂度为 $O(\log n)$ 的优秀性质,我们考虑先单独把 $2$ 操作放到线段树上实现。

先把线段树上代表 $[l,r]$ 的区间依次向叶子结点 $u|u\in[l,r]$ 连权值为 $0$ 的有向边,并从父亲到儿子结点连一条权值为 $0$ 的有向边。

如图,此时如果要将 $u$ 向区间 $[2,4]$ 连边,就改为把 $u$ 向 $[2,4]$ 拆成的线段树结点 $[2,2],[3,4]$ 连边即可,这样的正确性显然。

同理,对于区间向一个点连边的 $3$ 操作,我们可以从儿子向父亲结点连零权值有向边,并把线段树结点连向点 $u$。

但是两棵树显然不能放在一起,否则每个点的最短路都肯定是 $0$,于是考虑分开来做。

两边都按照之前说的来建树连边,但两棵树虽然形式上分离了,叶子结点是共用的,于是在对应的叶子结点之间连上双向零权边,对于操作 $2$,从第二棵树的叶子结点向第一棵树的线段树结点连边;对于操作 $3$,从第二棵树的线段树结点向第一棵树的叶子结点连边;单独的连边直接在第一棵树的叶子节点上连就好了,大概如下图:

最后修改:2021 年 08 月 13 日
如果觉得我的文章对你有用,请随意赞赏