Overview

This problem involves \(N\) products where you process \(Q\) queries that “select the product with the currently highest (or lowest) price, update its price (or cancel the update),” and then find the total price of all products at the end.

By combining a priority queue (heap) with Lazy Deletion, we can process each query efficiently.

Analysis

Naive Approach

If we scan the entire array to find the maximum or minimum value for each query, a single query takes \(O(N)\) time. Since there are \(Q\) queries, the overall time complexity becomes \(O(NQ)\), which will result in a Time Limit Exceeded (TLE) under the constraints \(N, Q \leq 2 \times 10^5\).

Therefore, we need a data structure that can efficiently retrieve and update the maximum and minimum values.

Searching for an Efficient Approach

A priority queue (heap) is a well-known data structure for efficiently managing maximum and minimum values. By preparing two heaps — a max-heap for managing the maximum value and a min-heap for managing the minimum value — we can retrieve the extreme values in \(O(1)\) each.

However, when a price is updated, directly deleting the “old price data before the update” from the heap would take \(O(N)\) time.

Solution via Lazy Deletion

Instead of directly deleting old data from the heap, we use the Lazy Deletion technique: “each time we extract data, we check whether it is up-to-date, and discard it if it is outdated.”

Specifically, we maintain an array P that records the “current correct price” of each product. When we extract an element (price, product_number) from the heap, we check whether that price matches P[product_number]. - If they match: This is the latest correct data, so we use it as the target for processing. - If they don’t match: This is outdated data from before a past update, so we discard it and extract the next element from the heap.

With this technique, there is no need to forcibly remove old data, enabling fast query processing.

---

Algorithm

1. Initialization

   • Initialize the array \(P\), which holds the current price of each product, with \(A\).
   • Initialize the total sum total_sum with \(\sum A\).
   • Add (-A[i], i) for each product \(i\) to the max-heap max_heap (since Python’s heapq is a min-heap, we negate the values to use it as a max-heap).
   • Add (A[i], i) for each product \(i\) to the min-heap min_heap.

2. Query Processing For each query \((T_j, X_j, R_j)\), perform the following operations:

   • If \(T_j = 1\) (select maximum):

     1. Keep popping elements (neg_p, i) from max_heap.
     2. When an element satisfying -neg_p == P[i] (matching the current price) is found, break out of the loop and target product \(i\).
     3. If \(R_j = 0\) (confirm):
        • Add \(X_j - P[i]\) to total_sum.
        • Update \(P[i]\) to \(X_j\).
        • Add the new price information to max_heap as (-X_j, i) and to min_heap as (X_j, i).
     4. If \(R_j = 1\) (cancel):
        • Since the price does not change, push the extracted latest information back to max_heap as (-P[i], i).

   • If \(T_j = 2\) (select minimum):

     • Perform the same operations using min_heap.

3. Final Output Output total_sum after all queries have been processed.

---

Complexity

• Time Complexity: \(O((N + Q) \log N)\) The total number of elements added to the heaps is at most \(O(N + Q)\), consisting of the initial \(N\) elements plus at most \(2\) elements added per query (one each to the max-heap and min-heap when \(R_j = 0\), or one pushed back when \(R_j = 1\)). Since pop operations are performed at most as many times as elements were added, and each heap operation takes \(O(\log N)\), the overall time complexity is \(O((N + Q) \log N)\), which comfortably fits within the time limit.

• Space Complexity: \(O(N + Q)\) The array \(P\) uses \(O(N)\) space, and the heaps store at most \(O(N + Q)\) elements, so the space complexity is \(O(N + Q)\).

---

Implementation Details

• Tiebreaking (selecting the product with the smallest product number) The problem states the rule: “When there are multiple products with the highest (lowest) price, select the one with the smallest product number.” Python’s tuple comparison, when the first elements (prices) are equal, proceeds to compare the second elements (index \(i\)).

  • Max-heap: By using (-price, i), the product with the maximum price becomes the one with the smallest -price and is prioritized first; if prices are equal, the one with the smaller \(i\) is prioritized.

  • Min-heap: By using (price, i), the product with the minimum price is prioritized first; if prices are equal, the one with the smaller \(i\) is prioritized. By designing the tuples this way, the standard behavior of the heap automatically satisfies the tiebreaking condition of the problem.

    Source Code

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    A = [int(x) for x in input_data[2:2+N]]
    
    P = list(A)
    total_sum = sum(A)
    
    max_heap = [(-val, i) for i, val in enumerate(A)]
    min_heap = [(val, i) for i, val in enumerate(A)]
    
    heapq.heapify(max_heap)
    heapq.heapify(min_heap)
    
    heappush = heapq.heappush
    heappop = heapq.heappop
    
    it = iter(input_data[2+N:])
    for _ in range(Q):
        t = int(next(it))
        x = int(next(it))
        r = int(next(it))
        
        if t == 1:
            while max_heap:
                neg_p, i = heappop(max_heap)
                if P[i] == -neg_p:
                    old_p = -neg_p
                    break
            
            if r == 0:
                P[i] = x
                heappush(max_heap, (-x, i))
                heappush(min_heap, (x, i))
                total_sum += x - old_p
            else:
                heappush(max_heap, (-old_p, i))
        else:
            while min_heap:
                p, i = heappop(min_heap)
                if P[i] == p:
                    old_p = p
                    break
                
            if r == 0:
                P[i] = x
                heappush(max_heap, (-x, i))
                heappush(min_heap, (x, i))
                total_sum += x - old_p
            else:
                heappush(min_heap, (old_p, i))
                
    print(total_sum)

if __name__ == '__main__':
    solve()

---

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