結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー miya145592
提出日時 2025-09-07 01:55:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,711 ms / 2,500 ms
コード長 2,345 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 170,216 KB
最終ジャッジ日時 2025-09-07 01:55:54
合計ジャッジ時間 37,943 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://nagiss.hateblo.jp/entry/2019/07/01/185421
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ALR = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
XYUV = [list(map(int, input().split())) for _ in range(Q)]
bit = Bit(M)
bit2 = Bit(M)
D = [i for i in range(N)]
for i in range(N):
    a, l, r = ALR[i]
    l-=1
    r-=1
    ALR[i] = (a, l, r)
    bit.add(i, a)
    bit2.add(l, 1)
    if r+1<M:
        bit2.add(r+1, -1)
minus = 0
plus = 0
for a, l, r in ALR:
    plus += (r-l+1)*a
    minus += bit.sum(r+1) - bit.sum(l)
for x, y, u, v in XYUV:
    x-=1
    y-=1
    u-=1
    v-=1
    xx = D[x]
    a, l, r = ALR[x]
    minus -= bit.sum(r+1) - bit.sum(l)
    tmp = bit2.sum(xx+1)
    if l<=xx<=r:
        minus -= (tmp-1)*a
    else:
        minus -= (tmp)*a
    bit.add(xx, -a)
    bit.add(y, a)
    bit2.add(l, -1)
    if r+1<M:
        bit2.add(r+1, 1)
    bit2.add(u, 1)
    if v+1<M:
        bit2.add(v+1, -1)
    minus += bit.sum(v+1) - bit.sum(u)
    tmp = bit2.sum(y+1)
    if u<=y<=v:
        minus += (tmp-1)*a
    else:
        minus += (tmp)*a
    ALR[x] = (a, u, v)
    D[x] = y
    plus -= (r-l+1)*a
    plus += (v-u+1)*a
    ans = plus-minus
    print(ans)
0