Day 158-Q5 — 削除できるナップサック（時間軸セグメント木によるオフライン化）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    q, W = int(data[0]), int(data[1])
    pos = 2
    items = []      # [w, v, 追加時刻, 削除時刻]
    query_cap = {}  # 時刻 -> 容量
    for t in range(q):
        typ = data[pos]
        if typ == b'1':
            items.append([int(data[pos + 1]), int(data[pos + 2]), t, q])
            pos += 3
        elif typ == b'2':
            items[int(data[pos + 1]) - 1][3] = t
            pos += 2
        else:
            query_cap[t] = int(data[pos + 1])
            pos += 2

    size = 1
    while size < q:
        size *= 2
    seg = [[] for _ in range(2 * size)]
    for w, v, s, e in items:            # 生存区間 [s, e) を O(log Q) 個のノードに載せる
        if w > W or s >= e:
            continue
        l, r = s + size, e + size
        while l < r:
            if l & 1:
                seg[l].append((w, v)); l += 1
            if r & 1:
                r -= 1; seg[r].append((w, v))
            l >>= 1; r >>= 1

    NEG = -1
    ans = {}
    stack = [(1, [0] + [NEG] * W)]      # dp[c] = 重さちょうど c での価値最大（NEG は到達不能）
    while stack:
        node, dp = stack.pop()
        for w, v in seg[node]:          # このノードに載った品物を 0/1 ナップサックで追加
            shifted = [x + v if x >= 0 else NEG for x in dp[:W + 1 - w]]
            dp = dp[:w] + list(map(max, dp[w:], shifted))
        if node >= size:
            t = node - size
            if t in query_cap:
                ans[t] = max(dp[:query_cap[t] + 1])
        else:                            # 子には「自分の dp」をそのまま渡す（子は新しいリストを作るので共有して安全）
            stack.append((2 * node + 1, dp))
            stack.append((2 * node, dp))

    sys.stdout.write("\n".join(str(ans[t]) for t in sorted(ans)) + ("\n" if ans else ""))


main()