Sliding Window RMQ

For subtask $1$, generate the sequence and scan every window of length $K$. For subtask $2$, overwrite the oldest value in a circular array of size $K$ and read the root of a segment tree for the current minimum.

For the full problem, keep candidate indices in a deque. Remove the front index if it is outside the current window. Before appending a new value $A_i$, remove all values at the back that are at least $A_i$. Then append the new value. Deque values increase strictly from front to back, so the front gives the current minimum. A removed value can never be better than the newer value in a later window. Every element enters and leaves the deque at most once, giving $O(N)$ time and $O(K)$ space.

$A_0$ itself is not part of any window. Compute $aA_{i-1}+c$ with 64-bit integers because it can exceed the 32-bit range.

Solution written by GPT6