线段树优化建图
感觉挺好玩的就写一个。 例题：CF786B 题目大意是，给定 q 次操作，有 3 种： 连边 u\to v 连边 u \to [l, r] 连边 [l, r] \to u 然后要跑一个最短路。那么很显然的是，如果你暴力建边，时间复杂度 O(nq) 显然会超时。那么这个时候可以考虑线段树优化建边。 拿有 5 个节点的图举例子。 先来说怎么做。 首先，显然，你需要一棵线段树。 你需要根据这棵线段树的 父子关系 来建边，并且权值为 0。 上树（入树）可以保证你可以从任意 区间 走到任意的 点。 然后再 […]