18.CF786B Legacy 线段树建图+最短路

18.CF786B Legacy 线段树建图+最短路

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定空图，要求支持 点-点连边、点-区间连边、区间-点连边。n次查询最短路

洛谷传送门：CF786B Legacy - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：B. Legacy (codeforces.com)

题目分析

将点-区间/区间-点转化为线段树到线段树节点连边的操作：我们建立在图上建立两棵线段树，一个父子向 0 0 0边，一个子父向 0 0 0边：

由于我们两棵树的叶子节点都代表相同的实点，因此我们需要在两棵线段树的叶子节点上双向建 0 0 0边：

对于区间连点，就在字父向树上二分到区间然后连边，点连区间则是父子向树上二分到区间连点。

如上图所示，紫线是点向区间连线，蓝线是区间向点连线。

注意所有的点都是叶节点，需要记录实编号，而不能直接用节点编号

完成全部操作后，直接对这个图跑 D i j k s t r a Dijkstra Dijkstra，求出源点到所有点的最短距离即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e6 + 10, MOD = 1e9 + 7, SN = 5e5;

namespace ffastIO {
	const int bufl = 1