CF1844F2 Min Cost Permutation (Hard Version)

本题与简单版本的唯一区别在于 $t$ 和 $n$ 的约束条件。 给定一个长度为 $n$ 的正整数数组 $a_1,\dots,a_n$，以及一个（可能为负数的）整数 $c$。 在数组 $a_1,\dots,a_n$ 的所有排列 $b_1,\dots,b_n$ 中，考虑最小化下式的值： $$ \sum_{i=1}^{n-1} |b_{i+1}-b_i-c| $$ 请找出能够取得该最小值的字典序最小的排列 $b$。 一个序列 $x$ 在字典序上小于序列 $y$ 当且仅当满足以下条件之一： - $x$ 是 $y$ 的前缀，且 $x \ne y$； - 在 $x$ 和 $y$ 第一个不同的位置，$x$ 的元素小于 $y$ 对应位置的元素。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $c$（$1 \le n \le 2 \cdot 10^5$，$-10^9 \le c \le 10^9$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1,\dots,a_n$（$1 \le a_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数 $b_1,\dots,b_n$，即能够取得最小值 $\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$ 的字典序最小的 $a$ 的排列。

在第一个测试用例中，可以证明 $\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$ 的最小值为 $27$，排列 $b = [9,3,1,4,5,1]$ 是能够取得该最小值的字典序最小的排列：$|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27$。 在第二个测试用例中，$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$ 的最小值为 $0$，$b = [1,3,5]$ 是能够取得该最小值的字典序最小的排列。 在第三个测试用例中，只有一种排列 $b$。 由 ChatGPT 4.1 翻译