Segment Tree
题目描述
给定无向带权图 G,含 2N+1 个顶点和 2N+1−1 条边。顶点编号为 0,1,…,2N,边编号为 1,2,…,2N+1−1。
图中的边分为 N+1 类,类型编号为 0,1,…,N。对于类型 i(0≤i≤N),恰有 2i 条边,编号依次为 2i,2i+1,…,2i+(2i−1)。
其中,对于 0≤j<2i,编号为 2i+j 的边连接顶点
j⋅2N−i和(j+1)⋅2N−i,
长度为 C2i+j。
例如,当 N=3 时,图如下。弧线或线段旁的数字表示边的编号,圆内数字表示顶点编号。

你需要依次处理 Q 个操作,分为两类:
- 1 j x:将边 j 的长度修改为 x。
- 2 s t:求从顶点 s 到顶点 t 的最短路径长度。
最短路径可以经过编号不在 [s,t] 内的顶点。
输入格式
第一行一个整数 N。
第二行 2N+1−1 个整数 C1,C2,…,C2N+1−1,表示所有边的初始长度。
第三行一个整数 Q。
接下来 Q 行,每行描述一个操作,格式为 1 j x 或 2 s t。
注意:顶点编号从 0 开始,而边编号从 1 开始。
输出格式
设共有 m 个第二类操作,输出 m 行。第 i 行输出第 i 个第二类操作的答案。
数据范围
所有输入均为整数。
- 1≤N≤18。
- 1≤Cj≤107。
- 1≤Q≤2×105。
- 第一类操作:1≤j≤2N+1−1,1≤x≤107。
- 第二类操作:0≤s<t≤2N。
- 保证至少有一个第二类操作。
样例
3
7 1 14 3 9 4 8 2 6 5 5 13 8 2 3
10
2 0 1
2 0 4
2 4 6
2 4 8
2 3 5
1 6 30
2 3 5
2 4 6
1 1 10000000
2 0 8
2
1
4
8
17
18
13
15
样例说明
- 第一个操作:使用边 8,沿 0→1 行走,距离为 2。
- 第二个操作:使用边 2,沿 0→4 行走,距离为 1。
- 第三个操作:使用边 6,沿 4→6 行走,距离为 4。
- 第四个操作:使用边 2,1,沿 4→0→8 行走,距离为 8。
- 第五个操作:使用边 11,6,13,沿 3→4→6→5 行走,距离为 17。
- 第六个操作将边 6 的长度由 4 修改为 30。
- 第七个操作:使用边 11,12,沿 3→4→5 行走,距离为 18。
- 第八个操作:使用边 2,1,15,14,沿 4→0→8→7→6 行走,距离为 13。
- 第九个操作将边 1 的长度由 7 修改为 10000000。
- 第十个操作:使用边 2,3,沿 0→4→8 行走,距离为 15。
来源
The 3rd Universal Cup Stage 21: Ōokayama,Problem C,原题为 Tokyo Tech Programming Contest 2024 Div.1 C。