結果

問題 No.2333 Slime Structure
コンテスト
ユーザー LyricalMaestro
提出日時 2025-07-05 03:17:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,322 ms / 3,000 ms
コード長 5,133 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 297,648 KB
最終ジャッジ日時 2025-07-05 03:18:56
合計ジャッジ時間 67,687 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

MIN_INT = -10 ** 18

from collections import deque

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

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        # [合計, 最大, 左最大, 右最大]
        self.array = [[MIN_INT, MIN_INT, MIN_INT, MIN_INT] for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i] = init_array[i]
        
        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

        self.left_queue = deque()
        self.right_queue = deque()

    def _op(self, array, left, right):
        if left[0] == MIN_INT and right[0] == MIN_INT:
            array[0] = MIN_INT
            array[1] = MIN_INT
            array[2] = MIN_INT
            array[3] = MIN_INT
        elif left[0] == MIN_INT:
            array[0] = right[0]
            array[1] = right[1]
            array[2] = right[2]
            array[3] = right[3]
        elif right[0] ==MIN_INT:
            array[0] = left[0]
            array[1] = left[1]
            array[2] = left[2]
            array[3] = left[3]
        else:
            # 合計値計算
            total = left[0] + right[0]

            # 左連続の中で最大値を計算
            left_max = max(left[2], left[0] + right[2])
            right_max = max(right[3], right[0] + left[3])

            # 最大計算
            max_value = max(left[1], right[1], left_max, right_max, left[3] + right[2])
            array[0] = total
            array[1] = max_value
            array[2] = left_max
            array[3] = right_max



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

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

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

        s = [MIN_INT, MIN_INT, MIN_INT, MIN_INT, MIN_INT]
        while len(self.left_queue) > 0:
            x = self.left_queue.popleft()
            self._op(s, s, self.array[x])
        while len(self.right_queue) > 0:
            x = self.right_queue.popleft()
            self._op(s, s, self.array[x])
        return s


def main():
    N = int(input())
    ab = []
    for _ in range(N):
        a, b = map(int, input().split())
        ab.append((a, b))

    Q = int(input())
    queriex = []
    for _ in range(Q):
        values = tuple(map(int, input().split()))
        queriex.append(values)
    
    # フォーカスすべき番号を集める
    focus_numbers = []
    f = 0
    for _, b in ab:
        focus_numbers.append(f)
        f += b
    focus_numbers.append(f)
    for values in queriex:
        if values[0] == 1:
            _, x, _ = values
            x -= 1
            focus_numbers.append(x - 1)
            focus_numbers.append(x)
            focus_numbers.append(x + 1)
        elif values[0] == 2:
            _, l, r = values
            l -= 1
            r -= 1 
            focus_numbers.append(l)
            focus_numbers.append(r)
            focus_numbers.append(r + 1)
    focus_numbers = list(set(focus_numbers))
    focus_numbers.sort()

    # 座標圧縮
    n_map = {}
    for i, f in enumerate(focus_numbers):
        n_map[f] = i
    n_max = len(focus_numbers)

    # 初期の値を入れていく
    array = []
    index = 0
    tot = 0
    for i in range(1, n_max):
        f1 = focus_numbers[i - 1]
        f2 = focus_numbers[i]
        while index < N and tot + ab[index][1] <= f1:
            tot += ab[index][1]
            index += 1
        a, _ = ab[index]
        array.append((a * (f2 - f1), a))

    # 初期の値を入れていく
    init_array = []
    for x, a in array:
        if x >= 0:
            init_array.append([x, x, x, x])
        else:
            init_array.append([x, a, a, a])
    
    seg_tree = SegmentTree(init_array)
    for values in queriex:
        if values[0] == 1:
            _, x, y = values
            x -= 1
            x_ = n_map[x]
            seg_tree.set(x_, y)
        else:
            _, l, r = values
            l -= 1
            r -= 1
            l_ = n_map[l]
            r_ = n_map[r]
            ans = seg_tree.calc_values(l_, r_ + 1)
            print(ans[1])


if __name__ == "__main__":
    main()
0