概要

\(N\) 個の商品があり、それぞれの初期価格が与えられます。価格の最大値または最小値を持つ商品を選択し、その価格を更新するクエリが \(Q\) 回与えられます。ただし、クエリによっては更新が取り消される（実質的に価格が変更されない）場合があります。すべてのクエリを処理した後の商品の合計価格を求める問題です。

値の動的な更新と、全体の最大値・最小値（およびそのインデックス）の取得を高速に行うため、セグメント木（Segment Tree） を用いて解くことができます。

---

考察

素朴なアプローチとその限界

各クエリにおいて、配列全体を走査して最大値や最小値を探す方法（シミュレーション）を考えてみます。 この場合、1回のクエリにつき \(O(N)\) の時間がかかります。クエリ数は \(Q\) 回あるため、全体の計算量は \(O(NQ)\) となります。 本問題では \(N, Q \le 2 \times 10^5\) であるため、最悪の場合に約 \(4 \times 10^{10}\) 回の計算が必要となり、実行時間制限（TLE）になってしまいます。

したがって、以下の操作を高速に行えるデータ構造が必要です。 1. 全体の中で「価格が最も高い（または低い）商品」のインデックスを特定する。 2. 特定した商品の価格を新しい値に更新する。

取り消しフラグ \(R_j\) の扱い

クエリの中には、価格変更を取り消す（\(R_j = 1\)）指示が含まれています。 手順をよく読むと、以下のことが分かります。 - \(R_j = 1\) のとき、商品の選択（手順1）は行われますが、最終的に価格は元の値に戻ります。 - つまり、\(R_j = 1\) のクエリは、他の商品の価格や今後のクエリに一切影響を与えません。

したがって、クエリを処理する際は、以下のように単純化できます。 - \(R_j = 0\) のとき：対象の商品を特定し、その商品の価格を \(X_j\) に更新する。 - \(R_j = 1\) のとき：対象の商品を特定するだけで、価格の更新は行わない（何もしない）。

---

アルゴリズム

動的な最大値・最小値の取得と更新を対数時間 \(O(\log N)\) で行うために、セグメント木 を使用します。

セグメント木の設計

セグメント木の各ノードには、その区間における以下の情報を保持させます。

• max_val: 区間内の最大価格
• max_idx: 最大価格を持つ商品のうち、最も小さい商品番号（インデックス）
• min_val: 区間内の最小価格
• min_idx: 最小価格を持つ商品のうち、最も小さい商品番号（インデックス）

2つの区間のマージ（op 関数）

2つの子ノード a と b の情報をマージして親ノードの情報を生成する演算 op(a, b) を定義します。

• 最大値の更新:
  • a.max_val > b.max_val なら、a の情報を採用。
  • a.max_val < b.max_val なら、b の情報を採用。
  • 値が等しい場合は、インデックスが小さい方（min(a.max_idx, b.max_idx)）を採用。
• 最小値の更新:
  • a.min_val < b.min_val なら、a の情報を採用。
  • a.min_val > b.min_val なら、b の情報を採用。
  • 値が等しい場合は、インデックスが小さい方（min(a.min_idx, b.min_idx)）を採用。

単位元（e 関数）

セグメント木の初期化や範囲外の参照で用いられる単位元 e() を定義します。 - 最大値の比較で邪魔をしないように、max_val は十分に小さな値（例：\(-1\)）にします。 - 最小値の比較で邪魔をしないように、min_val は十分に大きな値（例：\(2 \times 10^{18}\) などのインフィニティ）にします。 - インデックスは、min 選択で選ばれないように十分大きな値（例：\(10^9\)）にしておきます。

クエリの処理手順

1. セグメント木のルート（全体）の情報 seg.all_prod() を取得します。
2. \(T_j = 1\) なら max_idx を、\(T_j = 2\) なら min_idx を対象商品のインデックス idx とします。
3. \(R_j = 0\) の場合のみ、商品の価格を \(X_j\) に更新します。
   • セグメント木の idx 番目の要素を新しい価格情報 {X, idx, X, idx} に更新します。
   • 最終的な合計を計算するために、元の配列の価格 A[idx] も \(X_j\) に更新しておきます。

最後に、配列 A の総和を計算して出力します。

---

計算量

• 時間計算量: \(O(N + Q \log N)\)
  • セグメント木の構築に \(O(N)\) かかります。
  • 各クエリにおいて、全体の最大値・最小値の取得は \(O(1)\)、値の更新（\(R_j = 0\) のとき）は \(O(\log N)\) で行えます。クエリは \(Q\) 回あるため、クエリ処理全体で \(O(Q \log N)\) となります。
  • 最終的な価格の合計の計算に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • サイズ \(N\) の配列およびセグメント木を保持するため、空間計算量は \(O(N)\) となり、メモリ制限にも十分余裕があります。

---

実装のポイント

• タイブレークの処理: 「価格が等しい場合は商品番号が最も小さいものを選ぶ」というルールがあるため、マージ関数 op において値が等しい場合に min(a.idx, b.idx) を取る処理が非常に重要です。

• 単位元の値: 単位元 e() の min_val に設定する値は、商品の価格の最大値（\(10^9\)）よりも十分に大きい値にする必要があります。C++ではオーバーフローを防ぐために long long 型を使用し、十分大きな値を設定してください。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

struct S {
    long long max_val;
    int max_idx;
    long long min_val;
    int min_idx;
};

S op(S a, S b) {
    S res;
    if (a.max_val > b.max_val) {
        res.max_val = a.max_val;
        res.max_idx = a.max_idx;
    } else if (a.max_val < b.max_val) {
        res.max_val = b.max_val;
        res.max_idx = b.max_idx;
    } else {
        res.max_val = a.max_val;
        res.max_idx = min(a.max_idx, b.max_idx);
    }

    if (a.min_val < b.min_val) {
        res.min_val = a.min_val;
        res.min_idx = a.min_idx;
    } else if (a.min_val > b.min_val) {
        res.min_val = b.min_val;
        res.min_idx = b.min_idx;
    } else {
        res.min_val = a.min_val;
        res.min_idx = min(a.min_idx, b.min_idx);
    }
    return res;
}

S e() {
    return S{-1, 1000000000, 2000000000000000000LL, 1000000000};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    vector<long long> A(N);
    vector<S> init(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        init[i] = S{A[i], i, A[i], i};
    }

    segtree<S, op, e> seg(init);

    for (int j = 0; j < Q; ++j) {
        int T;
        long long X;
        int R;
        cin >> T >> X >> R;

        S root = seg.all_prod();
        int idx = (T == 1) ? root.max_idx : root.min_idx;

        if (R == 0) {
            A[idx] = X;
            seg.set(idx, S{X, idx, X, idx});
        }
    }

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += A[i];
    }
    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。