NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）F問題メモ

from operator import add


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


n, m, q = map(int, input().split())

queries = []
query3_count = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        query[1] -= 1
    elif query[0] == 2:
        query[1] -= 1
    else:
        query[1] -= 1
        query[2] -= 1
        query.append(query3_count)
        query3_count += 1
    queries.append(query)

rows_last_overwritten = [0] * n
rows_q3 = [set() for _ in range(n)]
cols = FenwickTreeInjectable(m + 1, int, add)
ans = [0] * query3_count

for query in reversed(queries):
    if query[0] == 1:
        l, r, x = query[1:]
        cols.add(l, x)
        cols.add(r, -x)
    elif query[0] == 2:
        i, x = query[1:]
        for j, qi in rows_q3[i]:
            ans[qi] += cols.sum(j) + x
        rows_q3[i].clear()
    else:
        i, j, qi = query[1:]
        rows_q3[i].add((j, qi))
        ans[qi] -= cols.sum(j)

for i in range(n):
    for j, qi in rows_q3[i]:
        ans[qi] += cols.sum(j)

print('\n'.join(map(str, ans)))