#P10310. [2023年重庆八中NOI模拟]warrior

    ID: 9428 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-快速选择随机采样同向双指针普通线段树

[2023年重庆八中NOI模拟]warrior

题目描述

给定长为 nn 的序列 SS。将它的每一个非空连续子数组各自升序排列,得到 n(n+1)2\frac{n(n+1)}2 个候选数组。两个不同的区间即使产生了同一个候选数组,也分别计入排名。

候选数组采用如下比较规则。找到在两个数组中出现次数不同的最小元素 xx,包含更多 xx 的那个数组更小。如果所有元素的出现次数都相同,两个数组相等。求按此规则排序后的第 kk 个数组。

输入格式

第一行两个整数 n,kn,k。第二行 nn 个整数 S1,…,SnS_1,\ldots,S_n。

输出格式

输出一行整数,表示第 kk 个数组,各元素按升序给出。

样例 1

3 2
1 3 2
1 3

六个数组依次是 [1,2,3][1,2,3]、[1,3][1,3]、[1][1]、[2,3][2,3]、[2][2]、[3][3]。

样例 2

31 32
1 4 1 9 3 6 1 4 1 9 3 7 1 1 4 5 1 4 1 9 1 9 8 1 1 9 2 6 8 1 7
1 1 1 1 1 1 1 1 1 2 3 3 4 4 4 5 6 6 7 8 8 9 9 9 9

样例 3

6 11
1 1 4 5 1 4
1 4 5

数据范围

1≤Si≤n≤1051\le S_i\le n\le10^5,1≤k≤n(n+1)21\le k\le\frac{n(n+1)}2。

子任务 分值 附加限制 依赖
1 40 n≤100n\le100
2 20 n≤1000n\le1000 1
3 10 n≤30000n\le30000,k≤100k\le100 1、2
4 n≤30000n\le30000,Si≤20S_i\le20
5 15 n≤30000n\le30000 1–4
6 5 无 1–5

原 PDF 题面