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 翻译