AT_ttpc2024_1_c Segment Tree

$ 2^N + 1 $ 頂点 $ 2^{N+1} - 1 $ 辺の無向グラフ $ G $ が与えられます。頂点には $ 0, 1, \dots, 2^N $ の番号が、辺には $ 1, 2, \dots, 2^{N+1}-1 $ の番号が割り振られています。 $ G $ の辺にはタイプ $ 0 $ からタイプ $ N $ までの $ N+1 $ 個の種類があります。 タイプ $ i $ $ (0 \le i \le N) $ の辺は全部で $ 2^i $ 本あり、番号 $ 2^i+0, 2^i+1, \dots, 2^i+(2^i-1) $ が割り当てられています。番号 $ 2^i + j $ $ (0 \le j \le 2^i-1) $ の辺は、頂点 $ j \times 2^{N-i} $ と頂点 $ (j+1) \times 2^{N-i} $ を結ぶ長さ $ C_{2^i + j} $ の無向辺です。 例えば $ N = 3 $ の場合、 $ G $ は以下のようなグラフになります。  $ Q $ 個のクエリが与えられるので、順に処理してください。与えられるクエリには以下の $ 2 $ 種類があります。 - `1 j x`: 辺 $ j $ の長さを $ x $ に変更する。 - `2 s t`: 頂点 $ s $ から頂点 $ t $ への最短経路の長さを求める。

入力は以下の形式で与えられる。頂点番号は $ 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 $

`2 s t` のクエリの個数を $ m $ として、 $ m $ 行出力せよ。そのうち $ i $ 行目には、 $ i $ 個目の `2 s t` のクエリの答えを出力せよ。

### 部分点 以下の制約を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 - `1 j x` のクエリが存在しない ### Sample Explanation 1 - $ 1 $ 個目のクエリでは、辺 $ 8 $ を用いて $ 0 \to 1 $ と移動することで最短距離 $ 2 $ を達成できます。 - $ 2 $ 個目のクエリでは、辺 $ 2 $ を用いて $ 0 \to 4 $ と移動することで最短距離 $ 1 $ を達成できます。 - $ 3 $ 個目のクエリでは、辺 $ 6 $ を用いて $ 4 \to 6 $ と移動することで最短距離 $ 4 $ を達成できます。 - $ 4 $ 個目のクエリでは、辺 $ 2, 1 $ を用いて $ 4 \to 0 \to 8 $ と移動することで最短距離 $ 8 $ を達成できます。 - $ 5 $ 個目のクエリでは、辺 $ 11, 6, 13 $ を用いて $ 3 \to 4 \to 6 \to 5 $ と移動することで最短距離 $ 17 $ を達成できます。 - $ 6 $ 個目のクエリでは、辺 $ 6 $ の長さを $ 4 $ から $ 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 $ から $ 10000000 $ に変更します。 - $ 10 $ 個目のクエリでは、辺 $ 2, 3 $ を用いて $ 0 \to 4 \to 8 $ と移動することで最短距離 $ 15 $ を達成できます。 ### Constraints - 入力はすべて整数 - $ 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` のクエリが $ 1 $ つ以上存在する