Antler Market Maker

# Antler Market Maker ## Problem Bessie runs the antler market at the MOOSACO county fair. She tracks the prices of antlers in a ledger that spans N consecutive stalls (numbered 1 to N). Each stall has an initial antler price. Every trading day, Bessie performs a series of operations: - **Range Add**: Increase all antler prices in a range [L, R] by a given amount D - **Range Max Query**: Find the maximum antler price in a range [L, R] As the market volatility increases, Bessie needs a fast way to handle these operations. Help her by implementing an efficient solution to process all queries and output the answers to each range max query. ## Input Format The first line contains two integers N and Q, where: - N = number of stalls - Q = number of operations The second line contains N integers representing the initial antler prices (space-separated). The next Q lines each contain one of two operations: 1. `max L R` – Find the maximum price in range [L, R] (1-indexed, inclusive) 2. `add L R D` – Add D to all prices in range [L, R] (1-indexed, inclusive) ## Output Format For each `max` query, output the maximum antler price in the given range on a separate line. ## Constraints - 1 ≤ N ≤ 100,000 - 1 ≤ Q ≤ 100,000 - 1 ≤ L ≤ R ≤ N - 1 ≤ Initial prices ≤ 1,000,000 - 1 ≤ D ≤ 1,000,000 ## Sample Input ``` 5 5 3 1 4 1 5 max 1 5 add 2 4 3 max 1 3 max 4 5 max 1 5 ``` ## Sample Output ``` 5 7 5 7 ``` ## Explanation Initial prices: [3, 1, 4, 1, 5] 1. **Query 1**: `max 1 5` – Maximum of [3, 1, 4, 1, 5] = 5 2. **Query 2**: `add 2 4 3` – Add 3 to positions 2-4. Prices become [3, 4, 7, 4, 5] 3. **Query 3**: `max 1 3` – Maximum of [3, 4, 7] = 7 4. **Query 4**: `max 4 5` – Maximum of [4, 5] = 5 5. **Query 5**: `max 1 5` – Maximum of [3, 4, 7, 4, 5] = 7