Overview

There are \(N\) products, each with a given initial price. You are given \(Q\) queries that select the product with the maximum or minimum price and update its price. However, some queries may be cancelled (effectively leaving the price unchanged). The problem asks you to find the total price of all products after processing all queries.

To efficiently perform dynamic value updates and retrieve the overall maximum/minimum values (along with their indices), this problem can be solved using a Segment Tree.

---

Analysis

Naive Approach and Its Limitations

Consider a method (simulation) that scans the entire array to find the maximum or minimum value for each query. In this case, each query takes \(O(N)\) time. Since there are \(Q\) queries, the overall time complexity is \(O(NQ)\). In this problem, \(N, Q \le 2 \times 10^5\), so in the worst case, approximately \(4 \times 10^{10}\) operations would be needed, resulting in a Time Limit Exceeded (TLE) verdict.

Therefore, we need a data structure that can efficiently perform the following operations: 1. Identify the index of the product with the highest (or lowest) price among all products. 2. Update the price of the identified product to a new value.

Handling the Cancellation Flag \(R_j\)

Some queries include an instruction to cancel the price change (\(R_j = 1\)). Reading the procedure carefully, we can observe the following: - When \(R_j = 1\), the product selection (step 1) is performed, but the price is ultimately restored to its original value. - In other words, queries with \(R_j = 1\) have absolutely no effect on other products’ prices or future queries.

Therefore, when processing queries, we can simplify as follows: - When \(R_j = 0\): Identify the target product and update its price to \(X_j\). - When \(R_j = 1\): Only identify the target product; do not update the price (do nothing).

---

Algorithm

To perform dynamic retrieval and updating of maximum/minimum values in logarithmic time \(O(\log N)\), we use a Segment Tree.

Segment Tree Design

Each node of the segment tree stores the following information about its interval:

• max_val: Maximum price in the interval
• max_idx: The smallest product number (index) among products with the maximum price
• min_val: Minimum price in the interval
• min_idx: The smallest product number (index) among products with the minimum price

Merging Two Intervals (op Function)

We define the operation op(a, b) that merges information from two child nodes a and b to produce the parent node’s information.

• Maximum value update:
  • If a.max_val > b.max_val, adopt a’s information.
  • If a.max_val < b.max_val, adopt b’s information.
  • If the values are equal, adopt the one with the smaller index (min(a.max_idx, b.max_idx)).
• Minimum value update:
  • If a.min_val < b.min_val, adopt a’s information.
  • If a.min_val > b.min_val, adopt b’s information.
  • If the values are equal, adopt the one with the smaller index (min(a.min_idx, b.min_idx)).

Identity Element (e Function)

We define the identity element e() used for segment tree initialization and out-of-range references. - To avoid interfering with maximum comparisons, max_val is set to a sufficiently small value (e.g., \(-1\)). - To avoid interfering with minimum comparisons, min_val is set to a sufficiently large value (e.g., \(2 \times 10^{18}\) or infinity). - Indices are set to a sufficiently large value (e.g., \(10^9\)) so they won’t be selected by min operations.

Query Processing Procedure

1. Retrieve the information from the root (entire range) of the segment tree using seg.all_prod().
2. If \(T_j = 1\), set the target product index idx to max_idx; if \(T_j = 2\), set it to min_idx.
3. Only when \(R_j = 0\), update the product’s price to \(X_j\).
   • Update the idx-th element of the segment tree with new price information {X, idx, X, idx}.
   • Also update the price A[idx] in the original array to \(X_j\) for computing the final total.

Finally, compute and output the sum of array A.

---

Complexity

• Time Complexity: \(O(N + Q \log N)\)
  • Building the segment tree takes \(O(N)\).
  • For each query, retrieving the overall maximum/minimum takes \(O(1)\), and updating a value (when \(R_j = 0\)) takes \(O(\log N)\). Since there are \(Q\) queries, the total query processing takes \(O(Q \log N)\).
  • Computing the final total price takes \(O(N)\).
• Space Complexity: \(O(N)\)
  • Since we maintain an array of size \(N\) and a segment tree, the space complexity is \(O(N)\), which is well within the memory limit.

---

Implementation Notes

• Tiebreaking: The rule states “if prices are equal, select the product with the smallest product number.” Therefore, in the merge function op, the handling of taking min(a.idx, b.idx) when values are equal is extremely important.

• Identity element values: The value set for min_val in the identity element e() must be sufficiently larger than the maximum possible product price (\(10^9\)). In C++, use the long long type to prevent overflow and set a sufficiently large value.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.