結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー Yoshio Yoshi
提出日時 2025-09-10 00:07:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,138 ms / 2,500 ms
コード長 2,952 bytes
コンパイル時間 553 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 115,004 KB
最終ジャッジ日時 2025-09-10 00:08:20
合計ジャッジ時間 50,021 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

class SegTree:
    # https://qiita.com/takayg1/items/c811bd07c21923d7ec69
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    N, M = map(int, input().split())
    IWI = [[0] * 4 for _ in range(N + 1)]
    
    init = [0] * (M + 1)  # 家[i] にいる人のレート
    def sf(x, y):
        return x + y
    
    for i in range(N):
        a, l, r = map(int, input().split())
        IWI[i + 1][0] = i + 1
        IWI[i + 1][1] = a
        IWI[i + 1][2] = l
        IWI[i + 1][3] = r

        init[i + 1] = a

    st = SegTree(init, sf, 0)
    bit = Bit(M + 1) 
    ans = 0

    for i in range(1, N + 1):
        _, a, l, r = IWI[i]
        ans += a * (r - l + 1) - st.query(l, r + 1)
        bit.add(l, 1)
        bit.add(r + 1, -1)

    # print(ans)

    Q = int(input())
    for _ in range(Q):
        x, y, u, v = map(int, input().split())
        at, a, l, r = IWI[x]

        # 元の天才度を返却
        ans -= a * (r - l + 1) - st.query(l, r + 1)
        # print("query before", st.query(l, r + 1))
        
        st.update(at, 0)
        bit.add(l, -1)
        bit.add(r + 1, 1)
        
        ans += a * bit.sum(at)
        # print("jimoto before", lst.get(at))

        st.update(y, a)

        # 新しい天才度を加算
        ans += a * (v - u + 1) - st.query(u, v + 1)
        # print("query after", st.query(u, v + 1))

        ans -= a * bit.sum(y)
        # print("jimoto after", lst.get(y))

        bit.add(u, 1)
        bit.add(v + 1, -1)

        IWI[x][0] = y
        IWI[x][2] = u
        IWI[x][3] = v

        print(ans)

    return

main()
0