← 返回题目列表

AtCoder · ttpc2024_1_c

C. 线段树

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

给你一个无向图 G 与 2^N + 1 顶点和 2^{N+1} - 1 边缘。顶点已编号 0, 1, \dots, 2^N,并且边缘已编号 1, 2, \dots, 2^{N+1}-1.

每个边缘 G 属于其中之一 N+1 类型,范围从类型 0 输入 N.
对于类型 i (0 \le i \le N),正好有 2^i 边,已编号 2^i+0, 2^i+1, \dots, 2^i+(2^i-1)。边缘已编号 2^i + j (0 \leq j \leq 2^i - 1) 是长度为的无向边 连接顶点的 C_{2^i + j} 连接顶点 j \times 2^{N-i} 和顶点 (j+1) \times 2^{N-i}.

例如,当 N = 3, G 如下图所示:

你被给予 Q 要处理的查询。有两种类型的查询:

  • 1 j x:更改边缘长度 j to x.
  • 2 s t:找到从顶点开始的最短路径长度 s 到顶点 t.

约束

  • 所有输入值均为整数。
  • 1 \le N \le 18
  • 1 \le C_j \le 10^7 (1 \le j \le 2^{N+1}-1)
  • 1 \le Q \le 2 \times 10^5
  • 查询中 1 j x, 1 \le j \le 2^{N+1}-1 和 1 \le x \le 10^7.
  • 查询中 2 s t, 0 \le s < t \le 2^N.
  • 至少有一个 2 s t 查询。

部分分数

30 通过满足附加约束的测试集将获得分数:没有 1 j x 查询。


输入

输入按以下格式给出。请注意,顶点编号从 0,而边编号从 1.

N
C_1 C_2 \cdots C_{2^{N+1}-1}
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

在这里, \text{query}_i 代表 i第一个查询。每个查询均以下列格式之一给出:

1 j x
2 s t

输出

让 m 是该类型的查询数 2 s t。输出 m 行,其中 i- 第行包含以下问题的答案 i-th 2 s t 查询。


示例输入 1

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

示例输出 1

2
1
4
8
17
18
13
15
  • 在第一个查询中,使用边缘 8,路径 0 \to 1 的总距离为 2.
  • 在第二个查询中,使用边缘 2,路径 0 \to 4 的总距离为 1.
  • 在第三个查询中,使用边缘 6,路径 4 \to 6 的总距离为 4.
  • 在第四个查询中,使用边 2, 1,路径 4 \to 0 \to 8 的总距离为 8.
  • 在第 5 个查询中,使用边 11, 6, 13,路径 3 \to 4 \to 6 \to 5 的总距离为 17.
  • 第6个查询中,边的长度 6 更新自 4 to 30.
  • 在第 7 个查询中,使用边 11, 12,路径 3 \to 4 \to 5 的总距离为 18.
  • 在第 8 个查询中,使用边 2, 1, 15, 14,路径 4 \to 0 \to 8 \to 7 \to 6 的总距离为 13.
  • 第9个查询中,边的长度 1 更新自 7 to 10000000.
  • 在第 10 个查询中,使用边 2, 3,路径 0 \to 4 \to 8 的总距离为 15.