概要

\(N\) 個の商品の中から、各クエリで最高価格または最低価格の商品を選び、価格を変更する（ただし取り消される場合もある）操作を \(Q\) 回行った後の合計金額を求める問題です。

考察

重要な気づき

1. 取り消しフラグ \(R_j = 1\) の場合：手順 1 で商品は選ばれるが、手順 3 で変更が取り消されるため、結果として価格は変わりません。つまり「何もしない」のと同じ効果です。したがって、\(R_j = 0\) の場合のみ実際に価格を更新すればよいです。

2. 必要な操作：各クエリで以下を高速に行う必要があります。

   • 「最高価格の商品（同率なら番号最小）」を見つける
   • 「最低価格の商品（同率なら番号最小）」を見つける
   • ある商品の価格を更新する

素朴なアプローチの問題点

毎回全商品を走査して最大・最小を見つけると \(O(N)\) かかり、全体で \(O(NQ)\) となります。\(N, Q\) が最大 \(2 \times 10^5\) の場合、\(4 \times 10^{10}\) 回の操作となりTLEします。

解決方法

セグメント木を使えば、最大・最小の取得と点更新をそれぞれ \(O(\log N)\) で行えます。

アルゴリズム

セグメント木の設計

各ノードに以下の情報を持たせます： - max_val, max_idx：その区間の最大値と、最大値を達成する最小の商品番号 - min_val, min_idx：その区間の最小値と、最小値を達成する最小の商品番号

2つの子ノードの情報を統合する際： - 最大値の統合：値が大きい方を採用。同じなら番号が小さい方を採用。 - 最小値の統合：値が小さい方を採用。同じなら番号が小さい方を採用。

クエリ処理の流れ

1. セグメント木の根（ノード1）から最大/最小の商品番号を取得する。
2. \(R_j = 0\) なら、その商品の価格を \(X_j\) に更新し、合計金額も差分で更新する。
3. \(R_j = 1\) なら、何もしない。

具体例

商品: \([5, 3, 5]\)（番号1, 2, 3）

• \(T=1\)（最高価格を選ぶ）→ 価格5の商品が2つあるが、番号最小の商品1が選ばれる。
• \(X=2, R=0\) → 商品1の価格を2に変更。結果: \([2, 3, 5]\)

計算量

• 時間計算量: \(O(N + Q \log N)\)
  • セグメント木の構築に \(O(N)\)
  • 各クエリの処理に \(O(\log N)\)（根の参照 + 点更新）
• 空間計算量: \(O(N)\)（セグメント木の配列）

実装のポイント

• セグメント木のサイズを \(N\) 以上の最小の2冪にする。\(N\) を超える葉には、最大値クエリに影響しない値（0）と最小値クエリに影響しない値（\(10^{18}\)）を入れておく。

• 合計金額は差分更新する。更新時に total += X - old_val とすることで毎回全体を再計算する必要がない。

• 取り消しフラグが1の場合は、対象商品の特定だけ行い（問題文の手順1に対応）、実際の更新はスキップする。

  ソースコード

import heapq

def main():
    import sys
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    A = [0] * N
    for i in range(N):
        A[i] = int(input_data[idx]); idx += 1
    
    # We need to efficiently find max (with smallest index tie-break) and min (with smallest index tie-break)
    # and support updates.
    # N, Q up to 2*10^5, so O(Q log N) is fine.
    
    # Use a sorted container approach with a balanced BST or segment tree.
    # Let's use a segment tree that stores (price, index) and supports:
    # - query max (max price, smallest index among max)
    # - query min (min price, smallest index among min)
    # - point update
    
    # Segment tree where each node stores:
    # - max_val, max_idx (the maximum price and smallest index achieving it)
    # - min_val, min_idx (the minimum price and smallest index achieving it)
    
    size = 1
    while size < N:
        size *= 2
    
    # Arrays for segment tree
    max_val = [0] * (2 * size)
    max_idx = [0] * (2 * size)
    min_val = [10**18] * (2 * size)
    min_idx = [0] * (2 * size)
    
    # Initialize leaves
    for i in range(N):
        pos = size + i
        max_val[pos] = A[i]
        max_idx[pos] = i
        min_val[pos] = A[i]
        min_idx[pos] = i
    
    # For positions beyond N, keep defaults (max=0, min=10^18) so they don't interfere
    for i in range(N, size):
        pos = size + i
        max_val[pos] = 0
        max_idx[pos] = size  # large index, won't be chosen
        min_val[pos] = 10**18
        min_idx[pos] = size
    
    def combine_max(v1, i1, v2, i2):
        if v1 > v2:
            return v1, i1
        elif v2 > v1:
            return v2, i2
        else:
            return v1, min(i1, i2)
    
    def combine_min(v1, i1, v2, i2):
        if v1 < v2:
            return v1, i1
        elif v2 < v1:
            return v2, i2
        else:
            return v1, min(i1, i2)
    
    # Build tree
    for i in range(size - 1, 0, -1):
        left = 2 * i
        right = 2 * i + 1
        max_val[i], max_idx[i] = combine_max(max_val[left], max_idx[left], max_val[right], max_idx[right])
        min_val[i], min_idx[i] = combine_min(min_val[left], min_idx[left], min_val[right], min_idx[right])
    
    def update(idx_item, val):
        pos = size + idx_item
        max_val[pos] = val
        max_idx[pos] = idx_item
        min_val[pos] = val
        min_idx[pos] = idx_item
        pos >>= 1
        while pos >= 1:
            left = 2 * pos
            right = 2 * pos + 1
            max_val[pos], max_idx[pos] = combine_max(max_val[left], max_idx[left], max_val[right], max_idx[right])
            min_val[pos], min_idx[pos] = combine_min(min_val[left], min_idx[left], min_val[right], min_idx[right])
            pos >>= 1
    
    total = sum(A)
    
    for _ in range(Q):
        T = int(input_data[idx]); idx += 1
        X = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        
        if T == 1:
            chosen_idx = max_idx[1]
        else:
            chosen_idx = min_idx[1]
        
        if R == 0:
            old_val = max_val[size + chosen_idx]  # current price
            total += X - old_val
            update(chosen_idx, X)
        # If R == 1, do nothing (change is cancelled)
    
    print(total)

main()

---

この解説は claude4.6opus-thinking によって生成されました。