Moamen and k-subarrays

题意翻译

给定一个大小为 $n$ 的数组。你可以将其分为 $k$ 个子数组，并按照每个子数组的字典序重新排列这些子数组，再顺次拼接，得到一个新的数组。问是否存在一种划分子数组的方案，使得重新拼接后的数组是单调不降的？ $t$ 组数据，$1\leqslant t\leqslant 1000$，$1\leqslant k\leqslant n\leqslant 10^5$，$0\leqslant |a_i|\leqslant 10^9$，$\sum n\leqslant 3\times 10^5$。 Translated by Eason_AC 2021.8.11

题目描述

Moamen has an array of $ n $ distinct integers. He wants to sort that array in non-decreasing order by doing the following operations in order exactly once: 1. Split the array into exactly $ k $ non-empty subarrays such that each element belongs to exactly one subarray. 2. Reorder these subarrays arbitrary. 3. Merge the subarrays in their new order. A sequence $ a $ is a subarray of a sequence $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Can you tell Moamen if there is a way to sort the array in non-decreasing order using the operations written above?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le |a_i| \le 10^9 $ ). It is guaranteed that all numbers are distinct. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3\cdot10^5 $ .

输出格式

For each test case, you should output a single string. If Moamen can sort the array in non-decreasing order, output "YES" (without quotes). Otherwise, output "NO" (without quotes). You can print each letter of "YES" and "NO" in any case (upper or lower).

输入输出样例

输入样例 #1

3
5 4
6 3 4 2 1
4 2
1 -4 0 -2
5 1
1 2 3 4 5

输出样例 #1

Yes
No
Yes

说明

In the first test case, $ a = [6, 3, 4, 2, 1] $ , and $ k = 4 $ , so we can do the operations as follows: 1. Split $ a $ into $ \{ [6], [3, 4], [2], [1] \} $ . 2. Reorder them: $ \{ [1], [2], [3,4], [6] \} $ . 3. Merge them: $ [1, 2, 3, 4, 6] $ , so now the array is sorted. In the second test case, there is no way to sort the array by splitting it into only $ 2 $ subarrays. As an example, if we split it into $ \{ [1, -4], [0, -2] \} $ , we can reorder them into $ \{ [1, -4], [0, -2] \} $ or $ \{ [0, -2], [1, -4] \} $ . However, after merging the subarrays, it is impossible to get a sorted array.