CF2259G Index Removal

一个数组 $b_1, b_2, \ldots, b_m$ 被称为“良好”的，如果对于每个 $i$ $(1 \leq i < m)$，有 $b_{i+1} \geq b_i$ 且 $b_{i+1} - b_i \leq k$。长度为 $1$ 的数组总是“良好”的。 现在给你一个初始为“良好”的数组 $a_1, a_2, \ldots, a_n$。请你对于每一个 $i$ $(1 \leq i \leq n)$ 独立地解决如下问题： - 移除 $a$ 的第 $i$ 个元素，使 $a = [a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n]$。你可以对 $a$ 中任意一个元素进行若干次操作，每次操作可以使某个元素减 $1$。请问最少需要多少次操作，才能使 $a$ 再次成为“良好”的数组？

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。保证初始的 $a$ 是一个“良好”的数组。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行 $n$ 个用空格分隔的整数，依次表示每个 $i$ 去掉第 $i$ 个元素后使数组重新变成“良好"所需的最少操作数。

在第一个测试用例中： - $i = 1$，$a = [2, 4, 5]$。此时 $a$ 仍然是“良好”的，无需操作。 - $i = 2$，$a = [1, 4, 5]$。我们只需对第 2 个元素操作一次（减去 1），使 $a = [1, 3, 5]$，此时数组是“良好”的。 - $i = 3$，$a = [1, 2, 5]$。我们对第 3 个元素操作一次（减去 1），得到 $a = [1, 2, 4]$，此时数组是“良好”的。 - $i = 4$，$a = [1, 2, 4]$。此时 $a$ 仍然是“良好”的，无需操作。 在第四个测试用例中，无论移除哪个元素，$a$ 都始终是“良好”的，所以每个下标的答案都是 $0$。 由 ChatGPT 5 翻译