Overview

This problem asks you to find the total price after performing \(Q\) operations on \(N\) products, where each query selects the product with the highest or lowest price and changes its price (though the change may be cancelled in some cases).

Analysis

Key Observations

1. When the cancellation flag \(R_j = 1\): The product is selected in step 1, but the change is cancelled in step 3, so the price remains unchanged. In other words, it has the same effect as “doing nothing.” Therefore, we only need to actually update the price when \(R_j = 0\).

2. Required operations: For each query, we need to efficiently perform the following:

   • Find “the product with the highest price (smallest index if tied)”
   • Find “the product with the lowest price (smallest index if tied)”
   • Update a product’s price

Issues with the Naive Approach

If we scan all products each time to find the maximum/minimum, it takes \(O(N)\) per query, resulting in \(O(NQ)\) overall. When \(N, Q\) are at most \(2 \times 10^5\), this amounts to \(4 \times 10^{10}\) operations, causing TLE.

Solution

Using a segment tree, we can perform maximum/minimum queries and point updates each in \(O(\log N)\).

Algorithm

Segment Tree Design

Each node stores the following information: - max_val, max_idx: The maximum value in the interval and the smallest product index achieving that maximum - min_val, min_idx: The minimum value in the interval and the smallest product index achieving that minimum

When merging information from two child nodes: - Maximum merge: Take the one with the larger value. If equal, take the one with the smaller index. - Minimum merge: Take the one with the smaller value. If equal, take the one with the smaller index.

Query Processing Flow

1. Obtain the product index with the maximum/minimum from the root (node 1) of the segment tree.
2. If \(R_j = 0\), update that product’s price to \(X_j\) and update the total price using the difference.
3. If \(R_j = 1\), do nothing.

Concrete Example

Products: \([5, 3, 5]\) (indices 1, 2, 3)

• \(T=1\) (select highest price) → There are two products with price 5, but product 1 is selected as it has the smallest index.
• \(X=2, R=0\) → Change product 1’s price to 2. Result: \([2, 3, 5]\)

Complexity

• Time complexity: \(O(N + Q \log N)\)
  • \(O(N)\) to build the segment tree
  • \(O(\log N)\) per query (root access + point update)
• Space complexity: \(O(N)\) (segment tree array)

Implementation Notes

• Set the segment tree size to the smallest power of 2 that is at least \(N\). For leaves beyond \(N\), insert values that don’t affect the maximum query (0) and values that don’t affect the minimum query (\(10^{18}\)).

• Update the total price using differences. By computing total += X - old_val during updates, there’s no need to recalculate the entire sum each time.

• When the cancellation flag is 1, only identify the target product (corresponding to step 1 in the problem statement) and skip the actual update.

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.