Loading...
Loading...
Loading...
A lab sensor in the college physics block logs n readings, numbered 1 to n. Readings can be negative.
A student then works through q lines, in order. A line min l r asks for the lowest reading from position l to position r, both included. A line set i x replaces reading i with x, because it was logged wrongly. Every later min must use the new values.
Print the answer to every min line.
min l r or set i x.min line, in order: the lowest reading from l to r at that moment.min line.Example
Input
6 7 5 2 8 -3 7 4 min 1 3 min 2 6 set 4 10 min 2 6 set 2 9 min 1 4 min 5 5
Output
2 -3 2 5 7
The lowest of 5, 2, 8 is 2, and the lowest of positions 2–6 is −3. After −3 becomes 10, positions 2–6 give 2. After 2 becomes 9, positions 1–4 hold 5, 9, 8, 10, so the answer is 5. Position 5 alone is 7.
Try the problem first. Open one hint at a time.
Scanning from l to r for every min costs up to n steps, which is 4 × 10^10 steps in the worst case.
A table of answers built once is fast to read, but a single set can change many of its entries.
Use a segment tree: each node keeps the lowest reading of one part of the list, and a node's part is split in half between its two children.
A set changes one leaf and the nodes above it. A min combines the few nodes that cover l to r exactly. Parts that lie outside l to r must not change the answer.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor