K-Increasing - Problem Statement

Make array $k$-increasing: $a[i] \leq a[i+k]$ for all valid $i$. Minimum changes. Split into $k$ independent subarrays: indices $\{0, k, 2k, ...\}$, $\{1, k+1, 2k+1, ...\}$, etc. Each subarray must be non-decreasing. Apply Slope Trick to each independently. Total $cost = sum$ of costs for each subarray. Time: $O(n \log n)$

Time complexity: $O(n \log n)$ overall. Split into $k$ independent subproblems. Each subproblem is a standard non-decreasing array problem.

Space complexity: $O(n)$ for the dp arrays.