CF2128E2.Submedians (Hard Version)

这是该问题的困难版本。唯一的区别在于本版本中，你需要为所有的“子中位数”找到一个对应的子数组。

只有当你解决了两个版本的问题时，才能进行 hack。

对于一个长度为 $m$ 的数组 $b$，如果整数 $v$ 满足以下条件，则称 $v$ 是 $b$ 的中位数：

• $v$ 大于等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素，并且
• $v$ 小于等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素。

例如：

• $[9, 3, 7]$ 的唯一中位数是 $7$，
• $[5, 3, 7, 9]$ 的中位数是 $5$、$6$ 和 $7$，
• $[2, 2, 2]$ 的唯一中位数是 $2$。

给定一个整数 $k$ 和一个由 $1$ 到 $n$ 之间的整数构成的数组 $a_1, \ldots, a_n$。

如果存在至少一对下标 $(l, r)$ 满足：

• $1 \leq l \leq r \leq n$，
• $r - l + 1 \geq k$，
• $v$ 是子数组 $[a_l, \ldots, a_r]$ 的中位数，

则称 $1$ 到 $n$ 之间的整数 $v$ 是一个“子中位数”。

请找出所有的子中位数，并且对于每一个子中位数，给出任意一组对应的下标对 $(l, r)$。

每组测试数据包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 50\,000$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 300\,000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。

保证所有测试用例中 $n$ 的总和不超过 $300\,000$。

对于每个测试用例，按如下格式输出答案。

第一行输出 $c$，即子中位数的个数。

接下来的 $c$ 行中，第 $i$ 行输出三个整数 $v_i$、$l_i$、$r_i$，满足：

• $r_i - l_i + 1 \geq k$，
• $v_i$ 是子数组 $[a_{l_i}, \ldots, a_{r_i}]$ 的一个中位数。

每个子中位数只需输出一次，即 $v_1, \ldots, v_c$ 必须互不相同。输出顺序不限。

如果有多种方案，可以输出任意一种。

在第一个测试用例中，长度至少为 $k = 3$ 的子数组有：

• $(l = 1, r = 3)$：$[4, 1, 2]$，唯一的中位数是 $2$，
• $(l = 2, r = 4)$：$[1, 2, 4]$，唯一的中位数是 $2$，
• $(l = 1, r = 4)$：$[4, 1, 2, 4]$，中位数是 $2$、$3$ 和 $4$。

在第二个测试用例中，一种可能的输出为：

• $(l = 4, r = 5)$：$[2, 1]$，中位数是 $1$ 和 $2$，
• $(l = 1, r = 5)$：唯一的中位数是 $2$，
• $(l = 3, r = 4)$：$[3, 2]$，中位数是 $2$ 和 $3$。

所有这些子数组的长度都至少为 $2$。注意可以证明，没有长度至少为 $2$ 的子数组的中位数为 $4$ 或 $5$。

由 ChatGPT 4.1 翻译