寻找一个最长的，拥有尽可能最大的第k小的数的子数列问题的快速算法

Question

一道学校内部oj上的题。原题英文，翻译过来是这样的：

输入三个整数n,m,k与一个数列{an}（一共有n个元素）,{an}内部的元素各不相同。请找到{an}的一个最长子数列，要求其第k小的元素尽可能大。

输入
第一行为一个整数T，表示测试组数。(1 <= T <= 10)
每一组都以三个整数开头,分别是n，m，k。(1 <= n <= 300000, 1 <= k <= m <= n)
接下来是n个整数，为{an}内部的元素。(1 <= ai <= 10^7)

输出
一个整数，为该子序列的长度。

时间限制: 1 Sec 内存限制: 128 MB

样例输入
4
5 3 2
1 5 3 2 4
8 3 3
1 5 6 2 4 7 8 3
8 7 3
6 5 4 1 7 2 3 8
8 1 1
4 3 2 6 7 8 5 1

样例输出
4
3
8
1

我的思路是用两个set维护第k小的值，从左到右遍历所有的长度为m的子数列，找到第k小的值最大的，并且长度为m的子数列的位置，让后让其左右扩张至最大。结果10组300000的数据大概需要8秒种，我的同学用了SBT树（完全没有用STL库+输入输出挂），大概需要4秒钟，然而时间限制是1秒钟。我们使用的是C++。请问有什么巧妙的算法能快速解决这道题？

很抱歉之前写成序列了，造成了误解。这个题要求找到的子数列完全对顺序没有要求。

Answer 1

这样的题目，最好举例说明：输入3个整数n,m,k为：12，4，2，数组an为[1,2,3,4,9,19,20,21,22,23,24,10]，输出结果应该是6，因为连续子序列有两个[1,2,3,4]和[19,20,21,22,23,24]，第2个元素分别是2和20,选大的，也就是[19,20,21,22,23,24]的长度，所以是6？

如果理解正确，应该不难做吧，一次遍历O(n)就可以，设置maxM和arrLength变量，放两个指针，slowPoz是子序列开始的位置，fastPoz是子序列结束的位置，首先看an[slowPoz+m]-an[slowPoz]是不是等于m，如果不是，那这个就不是连续子序列，slowPoz++，然后比较an[slowPoz+m]的值跟maxM的值，如果比maxM大，就替换maxM，fastPoz一直加到不是连续子序列为止，设置slowPoz=fastPoz,替换arrLength的值，继续下一循环。如果比maxM小，也p1++。循环结束返回arrLength就行。

Answer 2

经过助教的讲解，已解决。本题可能的最快的方法（至少比其他已知方法快）是，另开一个数组储存排好序了的an，通过二分法选取可能的最大第k小的值，然后用队列维护一个区间包含k-1个小于该可能值的元素。如果能成功，便能缩小二分区域。最终就可以找到包含最大的第k值的子数列，然后进行扩张得到最大长度。