A national rail operator runs a single high-speed line with M consecutive segments (1-indexed). Throughout the day, N reservation events arrive in chronological order.
There are two types of events:
1. `BOOK l r p`: A passenger has booked a journey across segments [l, r] contributing cost p. After this event, every segment in [l, r] increases its cumulative cost by p.
2. `QUERY l r`: Asks for the minimum cumulative cost among segments in [l, r] reflecting all preceding BOOK events.
The auditor wants to replay the day's log and emit one answer for every QUERY event.
Every run must ALSO produce one final value: the threshold-event index t (1 <= t <= N). That is, the 1-based event index after which some segment's cumulative cost first reaches or exceeds the threshold T (i.e. >= T). If no segment ever reaches T, output -1 as the final value.
Process the entire log efficiently for up to 2 * 10^5 events and 2 * 10^5 segments.
6 5 15 BOOK 1 3 5 QUERY 1 6 BOOK 4 6 10 QUERY 2 5 BOOK 3 4 6
0 5 5
M = 6 segments, N = 5 events, T = 15.
- Event 1 (BOOK 1 3 5): Segments 1..3 increase by 5 -> [5, 5, 5, 0, 0, 0]. Max cost is 5 < 15.
- Event 2 (QUERY 1 6): Minimum cost in segments [1, 6] is 0 -> output 0.
- Event 3 (BOOK 4 6 10): Segments 4..6 increase by 10 -> [5, 5, 5, 10, 10, 10]. Max cost is 10 < 15.
- Event 4 (QUERY 2 5): Minimum cost in segments [2, 5] is min(5, 5, 10, 10) = 5 -> output 5.
- Event 5 (BOOK 3 4 6): Segment 3 increases to 11, segment 4 increases from 10 to 16. Since 16 >= 15, segment 4 reaches threshold T at event 5!
Final threshold-event index is 5.
1. Build a Segment Tree with Lazy Propagation over M segments (1..M) initialized to 0. 2. Each tree node maintains: - `min_val`: minimum segment cost in this range. - `max_val`: maximum segment cost in this range. - `lazy`: pending range additions. 3. For each BOOK l r p: - Range add p to [l, r] using lazy propagation in O(log M). - Check if the global maximum cost (`tree[1].max_val`) is >= T. If so and `thresholdEvent == -1`, record `thresholdEvent = currentEventIndex`. 4. For each QUERY l r: - Query range minimum in [l, r] in O(log M) and print the result. 5. At the end, print `thresholdEvent`. 6. Total Time Complexity: O(N log M), Space Complexity: O(M).