U397746 Choose加强版

**数据范围 $n\le 5\times 10^5$，时间限制为 500ms，空间限制为 25MB，轻微卡常。** 对于一个长度为 $n$ 的序列 $a$ ，定义 $a$ 的极差表示 $a$ 中最大值与最小值之差；定义 $C(a,l,r)$ 表示 $a$ 的**连续**子序列 $[a_l,a_{l+1},\dots,a_r]$，其中 $1\le l\le r\le n$。

给定一个长度为 $n$ 的序列 $a$。 你需要选出 $a$ 的 $k$ 个长度均为 $L$ $(1\le L\le n-k+1)$ 的不同**连续**子序列 $C(a,l_1,l_1+L-1),C(a,l_2,l_2+L-1),\dots,C(a,l_k,l_k+L-1)$，其中 $1\le l_1

无

无

**【样例 1 解释】** - $k=1$ 时，极差最大不超过 $4$，此时满足长度最短的一种方案为 $[1,2,3,4,5]$。 - $k=2$ 时，极差最大不超过 $3$，此时满足长度最短的一种方案为 $[1,2,3,4],[2,3,4,5]$。 - $k=3$ 时，极差最大不超过 $2$，此时满足长度最短的一种方案为 $[1,2,3],[2,3,4],[3,4,5]$。 **【数据规模与约定】** 对于 $100\%$ 的数据，$1\le T\le 10$，$1\le n\le 5\times 10^5$，$1\le k\le n$，$-10^9\le a_i\le 10^9$。