#1171456 (PyPy3) No.2640 traO Stamps

• 問題: No.2640 traO Stamps
• ユーザー: LyricalMaestro
• 提出日時: 2026-07-15 01:37:30
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 515 ms / 2,000 ms
• コード長: 3,504 bytes
• コンパイル時間: 574 ms
• コンパイル使用メモリ: 96,100 KB
• 実行使用メモリ: 167,644 KB
• 最終ジャッジ日時: 2026-07-15 01:38:01
• 合計ジャッジ時間: 17,333 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 33

ソースコード

## https://yukicoder.me/problems/no/2640

from collections import deque

MAX_INT = 10 ** 18


class SegmentTree:
    """
    非再帰版セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    """

    def __init__(self, init_array, matrix):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.matrix = matrix
        self.array = [[MAX_INT] * 3 for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i][0] = a
            self.array[self.size + i][1] = a
            self.array[self.size + i][2] = 0
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self._op(self.array[i], self.array[2 * i], self.array[2 * i + 1])
            end_index = start_index
            start_index = end_index // 2
    
    def _op(self, array, left, right):
        if left[0] == MAX_INT:
            array[0] = right[0]
            array[1] = right[1]
            array[2] = right[2]
        elif right[0] == MAX_INT:
            array[0] = left[0]
            array[1] = left[1]
            array[2] = left[2]
        else:
            array[0] = left[0]
            array[1] = right[1]
            array[2] = left[2] + right[2] + self.matrix[right[0]][left[1]]

    def add(self, x, a):
        index = self.size + x
        self.array[index][0] = a
        self.array[index][1] = a
        while index > 1:
            index //= 2
            self._op(self.array[index], self.array[2 * index], self.array[2 * index + 1])

    def get_dist(self, l, r):
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        r_queue = deque()
        l_queue = deque()
        while L < R:
            if R & 1:
                R -= 1
                r_queue.appendleft(R)
            if L & 1:
                l_queue.append(L)
                L += 1
            L >>= 1; R >>= 1

        s = [MAX_INT] * 3
        while len(l_queue) > 0:
            new_s = [MAX_INT] * 3
            self._op(new_s, s, self.array[l_queue.popleft()])
            s = new_s
        while len(r_queue) > 0:
            new_s = [MAX_INT] * 3
            self._op(new_s, s, self.array[r_queue.popleft()])
            s = new_s
        return s


def main():
    N, M, K = map(int ,input().split())
    S = list(map(int, input().split()))
    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        edges.append((a - 1, b - 1, c))
    
    Q = int(input())
    txy = []
    for _ in range(Q):
        t, x, y = map(int ,input().split())
        txy.append((t, x, y))
    
    # 藩同士の移動時間を計算
    matrix = [[MAX_INT] * N for _ in range(N)]
    for i in range(N):
        matrix[i][i] = 0
    for a, b, c in edges:
        matrix[a][b] = min(matrix[a][b], c)
        matrix[b][a] = min(matrix[b][a], c)
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
    s_list = [s - 1 for s in S]
    seg_tree = SegmentTree(s_list, matrix)
    for t, x, y in txy:
        if t == 1:
            y -= 1
            seg_tree.add(x, y)
        elif t == 2:
            ans = seg_tree.get_dist(x, y + 1)
            print(ans[2])















if __name__ == "__main__":
    main()