結果

問題 No.789 範囲の合計
コンテスト
ユーザー norioc
提出日時 2025-03-11 03:04:01
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,001 bytes
コンパイル時間 593 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 183,340 KB
最終ジャッジ日時 2025-03-11 03:04:05
合計ジャッジ時間 4,332 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 


class DynamicSegTree:
    def __init__(self, op, e, size):
        self.op = op
        self.e = e
        self.size = size  # [0, size)
        self.data = {}

    def _update(self, p, x, k, l, r):
        """
        再帰的に p 番目の値を x に更新し、区間情報を更新する
          k: 現在のノード番号（根は 1）
          [l, r): 現在の区間
        """
        if r - l == 1:
            self.data[k] = x
            return x

        mid = (l + r) // 2
        if p < mid:
            self._update(p, x, 2 * k, l, mid)
        else:
            self._update(p, x, 2 * k + 1, mid, r)

        lval = self.data.get(2 * k, self.e)
        rval = self.data.get(2 * k + 1, self.e)
        self.data[k] = self.op(lval, rval)
        return self.data[k]

    def set(self, p: int, val):
        """位置 p の値を x に更新 (一点更新)"""
        self._update(p, val, 1, 0, self.size)

    def _prod(self, a, b, k, l, r):
        """
        再帰的に区間 [a, b) のクエリを行う
          k: 現在のノード番号（根は 1）
          [l, r): 現在の区間
        """
        if r <= a or b <= l:
            return self.e  # 完全に区間外の場合は単位元
        if a <= l and r <= b:
            return self.data.get(k, self.e)
        mid = (l + r) // 2
        vl = self._prod(a, b, 2 * k, l, mid)
        vr = self._prod(a, b, 2 * k + 1, mid, r)
        return self.op(vl, vr)

    def prod(self, l, r):
        """区間取得 [l, r)"""
        return self._prod(l, r, 1, 0, self.size)

    def get(self, p):
        assert 0 <= p <= self.size
        return self.prod(p, p + 1)


N = int(input())


dsegt = DynamicSegTree(lambda a, b: a+b, 0, 10**9+10)
ans = 0
for _ in range(N):
    qs = list(map(int, input().split()))
    if qs[0] == 0:
        x, y = qs[1], qs[2]
        dsegt.set(x, dsegt.get(x) + y)
    elif qs[0] == 1:
        l, r = qs[1], qs[2]
        res = dsegt.prod(l, r+1)
        ans += res

print(ans)
0