P10235 [yLCPC2024] C. MaiMai Basic Practice.

While playing MaiMai dx, Fusu found that a song can be split into at most $k$ segments for separate practice. Specifically, the song has $n$ notes, and each note has a difficulty value. The difficulty of the $i$-th note is $a_i$. Fusu thinks that the notes in a segment should become as difficult as possible. Therefore, for an interval $[l, r]$ of the note sequence, she defines the “non-beauty” of this interval as the number of **inversion pairs** in this interval. The **number of inversion pairs** in an interval $[l, r]$ is defined as the number of pairs $(i, j)$ such that $l \leq i < j \leq r$ and $a_i > a_j$. Fusu wants to partition the song into at most $k$ subsegments, so that every note belongs to at least one subsegment, and the maximum non-beauty among all segments is as small as possible. Formally, you need to split it into $t \leq k$ intervals $[l_1, r_1], [l_2, r_2], \dots [l_t, r_t]$, satisfying: - $l_1 = 1$, $r_t = n$. - For $1 \leq i < t$, $r_i + 1 = l_{i + 1}$. - For $1 \leq i \leq t$, $l_i \leq r_i$. Let $f(l, r)$ denote the non-beauty of interval $[l, r]$. Minimize $\max\limits_{i = 1}^t f(l_i, r_i)$.

**This problem contains multiple test cases within a single test file**. The first line contains a positive integer $T$, the number of test cases. For each test case: The first line contains two integers $n, k$ ($1 \leq k \leq n \leq 10^5$), representing the number of notes in the song and the maximum number of segments. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$), representing the difficulty of each note. It is guaranteed that the sum of $n$ over all test cases within a single test file does not exceed $10^5$.

For each test case, output one line with one integer, representing the answer.

Translated by ChatGPT 5