Range and Partition

题意翻译

给定一个长度为 $n$ 的数组 $a$。你需要确定一个范围 $[x,y]$，并将 $a$ 数组分成 $k$ 段，使得对于每一段，在范围 $[x,y]$ 以内的元素个数**大于**在范围 $[x,y]$ 以外的元素个数。请求出任意一组使得 $y-x$ 最小的 $x,y$ 和划分的方案。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 3\times 10^4$。 - $1\leqslant k\leqslant n\leqslant 2\times 10^5$，$\sum n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant n$。 Translated by Eason_AC 2022.1.28

题目描述

Given an array $ a $ of $ n $ integers, find a range of values $ [x, y] $ ( $ x \le y $ ), and split $ a $ into exactly $ k $ ( $ 1 \le k \le n $ ) subarrays in such a way that: - Each subarray is formed by several continuous elements of $ a $ , that is, it is equal to $ a_l, a_{l+1}, \ldots, a_r $ for some $ l $ and $ r $ ( $ 1 \leq l \leq r \leq n $ ). - Each element from $ a $ belongs to exactly one subarray. - In each subarray the number of elements inside the range $ [x, y] $ (inclusive) is strictly greater than the number of elements outside the range. An element with index $ i $ is inside the range $ [x, y] $ if and only if $ x \le a_i \le y $ . Print any solution that minimizes $ y - x $ .

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 3 \cdot 10^4 $ ) — the number of test cases. 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 2 \cdot 10^5 $ ) — the length of the array $ a $ and the number of subarrays required in the partition. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) where $ a_i $ is the $ i $ -th element of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case, print $ k+1 $ lines. In the first line, print $ x $ and $ y $ — the limits of the found range. Then print $ k $ lines, the $ i $ -th should contain $ l_i $ and $ r_i $ ( $ 1\leq l_i \leq r_i \leq n $ ) — the limits of the $ i $ -th subarray. You can print the subarrays in any order.

输入输出样例

输入样例 #1

3
2 1
1 2
4 2
1 2 2 2
11 3
5 5 5 1 5 5 1 5 5 5 1

输出样例 #1

1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11

说明

In the first test, there should be only one subarray, which must be equal to the whole array. There are $ 2 $ elements inside the range $ [1, 2] $ and $ 0 $ elements outside, if the chosen range is $ [1, 1] $ , there will be $ 1 $ element inside ( $ a_1 $ ) and $ 1 $ element outside ( $ a_2 $ ), and the answer will be invalid. In the second test, it is possible to choose the range $ [2, 2] $ , and split the array in subarrays $ (1, 3) $ and $ (4, 4) $ , in subarray $ (1, 3) $ there are $ 2 $ elements inside the range ( $ a_2 $ and $ a_3 $ ) and $ 1 $ element outside ( $ a_1 $ ), in subarray $ (4, 4) $ there is only $ 1 $ element ( $ a_4 $ ), and it is inside the range. In the third test, it is possible to choose the range $ [5, 5] $ , and split the array in subarrays $ (1, 4) $ , $ (5, 7) $ and $ (8, 11) $ , in the subarray $ (1, 4) $ there are $ 3 $ elements inside the range and $ 1 $ element outside, in the subarray $ (5, 7) $ there are $ 2 $ elements inside and $ 1 $ element outside and in the subarray $ (8, 11) $ there are $ 3 $ elements inside and $ 1 $ element outside.