U619825 碰大碰车站

awa

给定 $2^n+1$ 个点，标号为 $0$ 到 $2^n$。 对区间 $[1,n]$ 建立标准线段树，即记 $l_i$ 为节点 $i$ 的左端点，$r_i$ 为节点 $i$ 的右端点，$ls_i$ 为节点 $i$ 的左儿子，$rs_i$ 为节点 $i$ 的右儿子，$m_i = \lfloor\dfrac{l_i+r_i}{2}\rfloor$，则线段数的根节点为 $1$，且 $\forall i$，都有 $ls_i = 2i,rs_i = 2i+1$，并且 $l_{ls_i} = l_i,r_{ls_i} = m_i,l_{rs_i} = m_i+1,r_{rs_i} = r_i$。 然后定义 $w_i$ 为点 $l_i-1$ 和 $r_i$ 之间有一条权值为 $w_i$ 的无向边。 支持单点修改节点 $w_i$。 $q$ 次询问求出给定两点之间最短路长度。

第一行两个整数 $n,o$，分别表示 $n$ 和测试点编号（没用）。 第二行 $2^{n+1}-1$ 个整数，第 $i$ 个整数表示 $w_i$。 第三行一个整数 $q$，表示执行 $q$ 次操作。 接下来 $q$ 行每行三个整数 $op,u,v$。 如果 $op=1$，表示将节点 $u$ 的权值修改为 $v$。 如果 $op=2$ 表示查询点 $u,v$ 之间的最短距离。

对于每次查询输出一行一个整数。

$1 \leq n \leq 18$，$1 \leq q \leq 2e5$，$1 \leq w_i \leq 1e7$。