Company: Zorvyn SDE_4april
Difficulty: medium
Q3 Stock Price Queries 10 marks | 3s limit | 256MB You are analyzing stock prices over N days. The price on day i is P[i] . You need to process Q queries of two types: Update Query (Type 1): 1 i x - Update the price on day i to x . Range Query (Type 2): 2 l r - Find the maximum profit that could be made by buying on some day b and selling on some day s where l <= b < s <= r . The profit is P[s] - P[b] . You must buy before selling ( b < s ). If no profit is possible (all prices are non-increasing in the range), output 0 . Input Format First line contains two space-separated integers N and Q . Second line contains N space-separated integers representing prices P[1], P[2], ..., P[N] . Next Q lines each contain a query. Output Format For each Type 2 query, print the maximum profit on a new line. Examples Example 1 Input: 5 4 3 1 4 1 5 2 1 5 2 2 4 1 3 2 2 1 5 Output: 4 3 4 Explanation: Query 1: Range [1,5] = [3,1,4,1,5]. Buy at day 2, sell at day 5. Profit = 4. Query 2: Range [