{"problem":{"name":"[yLCPC2024] C. 舞萌基本练习","description":{"content":"扶苏在游玩舞萌 dx 的过程中，发现一首歌可以分成不超过 $k$ 段分别进行练习。 具体来说，这首歌共有 $n$ 个音符，每个音符有一个难度值。第 $i$ 个音符的难度值为 $a_i$。扶苏觉得一段歌曲的音符的难度应该是尽可能变难的。因此对于音符序列的一个区间 $[l, r]$，她认为这段区间的『不优美度』是这段区间的**逆序对**数。 一个区间 $[l, r]$ 的**逆序对数**被定义为满","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10235"},"statements":[{"statement_type":"Markdown","content":"扶苏在游玩舞萌 dx 的过程中，发现一首歌可以分成不超过 $k$ 段分别进行练习。\n\n具体来说，这首歌共有 $n$ 个音符，每个音符有一个难度值。第 $i$ 个音符的难度值为 $a_i$。扶苏觉得一段歌曲的音符的难度应该是尽可能变难的。因此对于音符序列的一个区间 $[l, r]$，她认为这段区间的『不优美度』是这段区间的**逆序对**数。\n\n一个区间 $[l, r]$ 的**逆序对数**被定义为满足 $l \\leq i < j \\leq r$ 且 $a_i > a_j$ 的数对 $(i, j)$ 个数。\n\n扶苏希望把这首歌划分成不超过 $k$ 个子段，满足每个音符都至少属于一个子段，使得不优美度最大的段的不优美度尽可能小。\n\n形式化的，你需要划分出 $t \\leq k$ 个区间 $[l_1, r_1], [l_2, r_2], \\dots [l_t, r_t]$，满足：\n\n- $l_1 = 1$，$r_t = n$。\n- 对 $1 \\leq i < t$，$r_i + 1= l_{i + 1}$。\n- 对 $1 \\leq i \\leq t$，$l_i \\leq r_i$。\n\n定义 $f(l, r)$ 表示区间 $[l, r]$ 的不优美度，最小化 $\\max\\limits_{i = 1}^t f(l_i, r_i)$\n\n## Input\n\n**本题单个测试点内有多组测试数据**。第一行是一个正整数 $T$，表示数据组数。对每组数据：\n\n第一行是两个整数 $n,k$（$1 \\leq k \\leq n \\leq 10^5$），表示歌曲的音符数和最多的划分段数。  \n第二行有 $n$ 个整数 $a_1, a_2, \\dots, a_n$（$-10^9 \\leq a_i \\leq 10^9$），表示每个音符的难度。\n\n数据保证单个测试点内的 $n$ 之和不超过 $10^5$。\n\n## Output\n\n对每组数据，输出一行一个整数表示答案。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10235","tags":["二分","树状数组","洛谷原创","洛谷月赛"],"sample_group":[["2\n5 2\n1 3 2 5 4\n8 2\n4 2 3 6 7 1 8 5","1\n2"]],"created_at":"2026-03-03 11:09:25"}}