結果

問題 No.789 範囲の合計
ユーザー norioc
提出日時 2025-03-10 02:22:03
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,055 bytes
コンパイル時間 397 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 226,432 KB
最終ジャッジ日時 2025-03-10 02:22:07
合計ジャッジ時間 3,580 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 MLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Compression:
    def __init__(self, iterable):
        self.vs = sorted(set(iterable))
        self.n = len(self.vs)
        self.v2i = {}
        for i, val in enumerate(self.vs):
            self.v2i[val] = i

    def __len__(self):
        return self.n

    def index(self, val):
        """val のインデックスを返す"""
        return self.v2i[val]

    def value(self, index):
        """インデックスに対応する値を返す"""
        return self.vs[index]


class FenwickTree:
    def __init__(self, n):
        self.data = [0] * (n+10)
        self.n = (n+10)

    def add(self, p, x):
        assert 0 <= p < self.n
        p += 1
        while p < len(self.data):
            self.data[p] += x
            p += p & -p

    def sum(self, p):
        """区間 [0, p] の和"""
        assert 0 <= p < self.n
        p += 1
        s = 0
        while p > 0:
            s += self.data[p]
            p -= p & -p
        return s

    def rangesum(self, l, r):
        """区間 [l, r] の和"""
        assert 0 <= l <= r < self.n
        s = self.sum(r)
        if l > 0:
            s -= self.sum(l-1)
        return s


class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.lazy = 0
        self.left = None
        self.right = None


class DynamicSegmentTree:
    def __init__(self, start, end):
        self.root = Node(start, end)

    def updateRange(self, node, start, end, val):
        if node.lazy != 0:
            node.total += (node.end - node.start + 1) * node.lazy
            if node.start != node.end:
                if not node.left:
                    node.left = Node(node.start, (node.start + node.end) // 2)
                if not node.right:
                    node.right = Node((node.start + node.end) // 2 + 1, node.end)
                node.left.lazy += node.lazy
                node.right.lazy += node.lazy
            node.lazy = 0

        if node.start > end or node.end < start:
            return

        if node.start >= start and node.end <= end:
            node.total += (node.end - node.start + 1) * val
            if node.start != node.end:
                if not node.left:
                    node.left = Node(node.start, (node.start + node.end) // 2)
                if not node.right:
                    node.right = Node((node.start + node.end) // 2 + 1, node.end)
                node.left.lazy += val
                node.right.lazy += val
            return

        mid = (node.start + node.end) // 2
        if not node.left:
            node.left = Node(node.start, mid)
        if not node.right:
            node.right = Node(mid + 1, node.end)
        self.updateRange(node.left, start, end, val)
        self.updateRange(node.right, start, end, val)

        node.total = node.left.total + node.right.total

    def queryRange(self, node, start, end):
        if not node or start > node.end or end < node.start:
            return 0

        if node.lazy != 0:
            node.total += (node.end - node.start + 1) * node.lazy
            if node.start != node.end:
                if not node.left:
                    node.left = Node(node.start, (node.start + node.end) // 2)
                if not node.right:
                    node.right = Node((node.start + node.end) // 2 + 1, node.end)
                node.left.lazy += node.lazy
                node.right.lazy += node.lazy
            node.lazy = 0

        if start <= node.start and end >= node.end:
            return node.total

        return self.queryRange(node.left, start, end) + self.queryRange(node.right, start, end)


INF = 1 << 60
N = int(input())

dsegt = DynamicSegmentTree(0, INF)
ans = 0
for _ in range(N):
    qs = list(map(int, input().split()))
    if qs[0] == 0:  # a[x] += y
        x, y = qs[1]-1, qs[2]
        dsegt.updateRange(dsegt.root, x, x, y)
    elif qs[0] == 1: # [l, r]
        l, r = qs[1]-1, qs[2]-1
        res = dsegt.queryRange(dsegt.root, l, r)
        ans += res

print(ans)
0