Submission #70991335

---

Source Code Expand

# フェニック木 (binary indexed tree: BIT) クラス
class BIT:
    def __init__(self, size):
        self.__size = size
        self.__bit = [0] * (size + 1)

    # O(log N): インデックス idx の値に val を加算するメソッド
    def add(self, idx, val):
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & -idx

    # O(log N): 区間 1 ~ idx の和を求める計算用のメソッド
    def __sum(self, idx):
        result = 0
        while idx > 0:
            result += self.__bit[idx]
            idx -= idx & -idx
        return result

    # O(log N): 区間 1 ~ idx1 または 区間 idx1 ~ idx2 の和を求めるメソッド
    def get_sum(self, idx1, idx2 = None):
        if idx2 is None:
            return self.__sum(idx1)
        return self.__sum(idx2) - self.__sum(idx1 - 1)

n, q = map(int, input().split())
a = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]

SIZE = 5 * (10 ** 5) + 3
bit = BIT(SIZE)
total_bit = BIT(SIZE)
for i in range(n):
    bit.add(a[i] + 1, 1)
    total_bit.add(a[i] + 1, a[i])

for type, xl, yr in query:
    if type == 1:
        x, y = xl - 1, yr
        bit.add(a[x] + 1, -1)
        bit.add(y + 1, 1)
        total_bit.add(a[x] + 1, -a[x])
        total_bit.add(y + 1, y)
        a[x] = y
    else:
        l, r = xl, yr
        if l >= r:
            print(n * l)
        else:
            ans = r * bit.get_sum(r + 1, SIZE)
            ans += total_bit.get_sum(l + 2, r)
            ans += l * bit.get_sum(l + 1)
            print(ans)

Submission Info

Judge Result