結果

問題 No.3265 地元に帰れば天才扱い！
ユーザー elphe
提出日時 2025-08-18 10:32:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,425 ms / 2,500 ms
コード長 4,850 bytes
コンパイル時間 532 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 126,060 KB
最終ジャッジ日時 2025-09-06 12:35:29
合計ジャッジ時間 34,055 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

# PyPy3 互換に翻訳した C++23 コード

import sys
import threading
from operator import add

def main():
    input = sys.stdin.readline
    # -- 任意の結合関数に対応したセグメント木（点更新・区間クエリ） --
    class SegmentTree:
        __slots__ = ('n', 'size', 'func', 'default', 'data')
        def __init__(self, init_list, default, func):
            # init_list: 初期値リスト
            # default: 単位元
            # func(a, b): 結合関数（結合的）
            m = len(init_list)
            n = 1
            while n < m:
                n <<= 1
            self.n = n
            self.size = m
            self.func = func
            self.default = default
            # ツリー用の配列（サイズ 2*n）
            data = [default] * (2 * n)
            # 葉ノードに初期値をセット
            data[n:n+m] = init_list
            # 内部ノードを構築
            for i in range(n-1, 0, -1):
                data[i] = func(data[2*i], data[2*i+1])
            self.data = data

        def update(self, idx, value):
            # idx の位置を value に更新
            i = idx + self.n
            self.data[i] = value
            i >>= 1
            while i:
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])
                i >>= 1

        def query(self, left, right):
            # 区間 [left, right) のクエリを実行
            res_l = self.default
            res_r = self.default
            l = left + self.n
            r = right + self.n
            while l < r:
                if l & 1:
                    res_l = self.func(res_l, self.data[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res_r = self.func(self.data[r], res_r)
                l >>= 1
                r >>= 1
            return self.func(res_l, res_r)

    # 入力読み込み
    N, M = map(int, input().split())
    A = [0] * N
    L = [0] * N
    R = [0] * N
    for i in range(N):
        a, l, r = map(int, input().split())
        A[i] = a
        # 0-based インデックスに変換
        L[i] = l - 1
        R[i] = r - 1

    Q, = map(int, input().split())
    X = [0] * Q
    Y = [0] * Q
    U = [0] * Q
    V = [0] * Q
    for i in range(Q):
        x, y, u, v = map(int, input().split())
        X[i] = x - 1
        Y[i] = y - 1
        U[i] = u - 1
        V[i] = v - 1

    # 初期解の計算: B_init のプレフィックス和を利用
    B_init = [0] * (M + 1)
    addr_of = [0] * N
    # イモズ法用差分配列
    imos_init = [0] * (M + 1)

    for i in range(N):
        addr_of[i] = i
        B_init[i] = A[i]
        imos_init[L[i]] += 1
        # R[i]+1 が範囲内なら減算
        if R[i] + 1 <= M:
            imos_init[R[i] + 1] -= 1

    # B_init の累積和
    csum = [0] * (M + 2)
    for i in range(M + 1):
        csum[i+1] = csum[i] + B_init[i]

    cur_ans = 0
    for i in range(N):
        length = R[i] - L[i] + 1
        total_B = csum[R[i] + 1] - csum[L[i]]
        cur_ans += length * A[i] - total_B

    # セグメント木を構築
    B_tree = SegmentTree(B_init, 0, add)        # A を格納する木
    imos_tree = SegmentTree(imos_init, 0, add)  # カバレッジ数を管理する木

    ans = [0] * Q

    for qi in range(Q):
        seg = X[qi]
        # 古い区間のイモズ差分を更新
        old_l, old_r = L[seg], R[seg]
        cur = imos_tree.query(old_l, old_l+1) - 1
        imos_tree.update(old_l, cur)
        if old_r + 1 <= M:
            cur2 = imos_tree.query(old_r+1, old_r+2) + 1
            imos_tree.update(old_r+1, cur2)

        # 古い寄与分を差し引く
        cover_count = imos_tree.query(0, addr_of[seg] + 1)
        sum_B = B_tree.query(old_l, old_r + 1)
        cur_ans -= (old_r - old_l + 1) * A[seg] - sum_B - cover_count * A[seg]

        # B_tree から削除
        B_tree.update(addr_of[seg], 0)

        # 新しい区間・アドレスを設定して追加
        L[seg], R[seg] = U[qi], V[qi]
        addr_of[seg] = Y[qi]
        B_tree.update(addr_of[seg], A[seg])

        # 新しい寄与分を加算
        new_l, new_r = L[seg], R[seg]
        cover_count = imos_tree.query(0, addr_of[seg] + 1)
        sum_B = B_tree.query(new_l, new_r + 1)
        cur_ans += (new_r - new_l + 1) * A[seg] - sum_B - cover_count * A[seg]

        # 新しい区間のイモズ差分を登録
        cur3 = imos_tree.query(new_l, new_l+1) + 1
        imos_tree.update(new_l, cur3)
        if new_r + 1 <= M:
            cur4 = imos_tree.query(new_r+1, new_r+2) - 1
            imos_tree.update(new_r+1, cur4)

        ans[qi] = cur_ans

    # 解答を出力
    out = sys.stdout.write
    for v in ans:
        out(str(v) + '\n')

if __name__ == '__main__':
   main()
0