#P18237. Segment Tree

Segment Tree

Segment Tree

题目描述

给定无向带权图 GG,含 2N+12^N+1 个顶点和 2N+1−12^{N+1}-1 条边。顶点编号为 0,1,…,2N0,1,\ldots,2^N,边编号为 1,2,…,2N+1−11,2,\ldots,2^{N+1}-1。

图中的边分为 N+1N+1 类,类型编号为 0,1,…,N0,1,\ldots,N。对于类型 ii(0≤i≤N0\le i\le N),恰有 2i2^i 条边,编号依次为 2i,2i+1,…,2i+(2i−1)2^i,2^i+1,\ldots,2^i+(2^i-1)。

其中,对于 0≤j<2i0\le j<2^i,编号为 2i+j2^i+j 的边连接顶点

j⋅2N−i和(j+1)⋅2N−i,j\cdot2^{N-i}\quad\text{和}\quad(j+1)\cdot2^{N-i},

长度为 C2i+jC_{2^i+j}。

例如,当 N=3N=3 时,图如下。弧线或线段旁的数字表示边的编号,圆内数字表示顶点编号。

N=3时的图与边编号

你需要依次处理 QQ 个操作,分为两类:

  • 1 j x:将边 jj 的长度修改为 xx。
  • 2 s t:求从顶点 ss 到顶点 tt 的最短路径长度。

最短路径可以经过编号不在 [s,t][s,t] 内的顶点。

输入格式

第一行一个整数 NN。

第二行 2N+1−12^{N+1}-1 个整数 C1,C2,…,C2N+1−1C_1,C_2,\ldots,C_{2^{N+1}-1},表示所有边的初始长度。

第三行一个整数 QQ。

接下来 QQ 行,每行描述一个操作,格式为 1 j x 或 2 s t。

注意:顶点编号从 00 开始,而边编号从 11 开始。

输出格式

设共有 mm 个第二类操作,输出 mm 行。第 ii 行输出第 ii 个第二类操作的答案。

数据范围

所有输入均为整数。

  • 1≤N≤181\le N\le18。
  • 1≤Cj≤1071\le C_j\le10^7。
  • 1≤Q≤2×1051\le Q\le2\times10^5。
  • 第一类操作:1≤j≤2N+1−11\le j\le2^{N+1}-1,1≤x≤1071\le x\le10^7。
  • 第二类操作:0≤s<t≤2N0\le s<t\le2^N。
  • 保证至少有一个第二类操作。

样例

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

样例说明

  1. 第一个操作:使用边 88,沿 0→10\to1 行走,距离为 22。
  2. 第二个操作:使用边 22,沿 0→40\to4 行走,距离为 11。
  3. 第三个操作:使用边 66,沿 4→64\to6 行走,距离为 44。
  4. 第四个操作:使用边 2,12,1,沿 4→0→84\to0\to8 行走,距离为 88。
  5. 第五个操作:使用边 11,6,1311,6,13,沿 3→4→6→53\to4\to6\to5 行走,距离为 1717。
  6. 第六个操作将边 66 的长度由 44 修改为 3030。
  7. 第七个操作:使用边 11,1211,12,沿 3→4→53\to4\to5 行走,距离为 1818。
  8. 第八个操作:使用边 2,1,15,142,1,15,14,沿 4→0→8→7→64\to0\to8\to7\to6 行走,距离为 1313。
  9. 第九个操作将边 11 的长度由 77 修改为 1000000010000000。
  10. 第十个操作:使用边 2,32,3,沿 0→4→80\to4\to8 行走,距离为 1515。

来源

The 3rd Universal Cup Stage 21: Ōokayama,Problem C,原题为 Tokyo Tech Programming Contest 2024 Div.1 C。