CF1384B2 Koa and the Beach (Hard Version)

本题的简单版与困难版仅在数据范围上有所不同。本题为困难版，数据范围更大。只有在所有版本的题目都被解决后，你才能进行 Hack。 考拉 Koa 正在海滩上！ 海滩从左到右依次为岸边、$n+1$ 米的海域，以及距离岸边 $n+1$ 米处的一个小岛。 她测量了距离岸边 $1, 2, \dots, n$ 米处的海水深度，并将其记录在数组 $d$ 中。$d_i$ 表示距离岸边 $i$ 米处的海水深度，$1 \le i \le n$。 和所有海滩一样，这里也有潮汐，潮汐的强度用参数 $k$ 表示，并从 $t=0$ 时刻开始影响所有深度，具体如下： - 在连续 $k$ 秒内，每秒潮汐会使所有深度增加 $1$。 - 接着在连续 $k$ 秒内，每秒潮汐会使所有深度减少 $1$。 - 这个过程不断循环（即，深度增加 $k$ 秒，然后减少 $k$ 秒，如此往复）。形式化地，定义 $0$ 下标数组 $p = [0, 1, 2, \ldots, k-2, k-1, k, k-1, k-2, \ldots, 2, 1]$，长度为 $2k$。在时刻 $t$（$0 \le t$）时，距离岸边 $i$ 米处的深度为 $d_i + p[t \bmod 2k]$（$t \bmod 2k$ 表示 $t$ 除以 $2k$ 的余数）。注意每秒变化是瞬时发生的，具体可参考提示部分的说明。 在 $t=0$ 时，Koa 站在岸边，想要前往小岛。假设在某个时刻 $t$（$0 \le t$），她位于距离岸边 $x$ 米处（$0 \le x \le n$）： - 每秒 Koa 可以选择向前游 $1$ 米（$x$ 变为 $x+1$），也可以选择不游动（$x$ 保持不变），无论哪种情况，$t$ 都会加 $1$。 - 由于 Koa 游泳技术不好，她所处位置的海水深度在整数时刻不能超过 $l$（否则会溺水）。更正式地说，如果 Koa 在时刻 $t$（$t \ge 0$ 的整数）位于距离岸边 $x$ 米处（$1 \le x \le n$），那么该处的海水深度 $d_x + p[t \bmod 2k]$ 必须满足 $d_x + p[t \bmod 2k] \le l$。 - 一旦 Koa 到达距离岸边 $n+1$ 米的小岛，她就可以停下来休息。注意，Koa 在游动过程中不受潮汐影响（即游动时不会溺水）。此外，Koa 可以选择在岸边等待任意长时间，且岸边和小岛都不会受到潮汐影响（它们是坚实的陆地，Koa 在那里不会溺水）。 Koa 想知道她是否能够从岸边到达小岛。请你帮她判断！

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$k$ 和 $l$（$1 \le n \le 3 \cdot 10^5; 1 \le k \le 10^9; 1 \le l \le 10^9$），分别表示 Koa 测量的海域长度和参数 $k$、$l$。 每个测试用例的第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$（$0 \le d_i \le 10^9$），表示每一米处的海水深度。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例： 如果 Koa 能够从岸边到达小岛，输出 Yes，否则输出 No。 你可以用任意大小写输出每个字母。

在下述示例中，$s$ 表示岸边，$i$ 表示小岛，$x$ 表示 Koa 距离岸边的距离，下划线表示 Koa 的当前位置，数组中的值表示受潮汐影响后距离岸边 $1, 2, \dots, n$ 米处的当前深度。 在第 1 个测试用例中，$n = 2, k = 1, l = 1, p = [0, 1]$。 Koa 想从岸边（$x = 0$）到达小岛（$x = 3$）。以下是一种可行的方案： - 初始时刻 $t = 0$，海滩如下：$[\underline{s}, 1, 0, i]$。 - 若 $t = 0$ 时 Koa 选择游到 $x = 1$，则 $t = 1$ 时海滩为 $[s, \underline{2}, 1, i]$，由于 $2 > 1$，她会溺水。因此 Koa 选择等待 $1$ 秒，此时 $t = 1$，海滩为 $[\underline{s}, 2, 1, i]$。 - $t = 1$ 时 Koa 游到 $x = 1$，$t = 2$ 时海滩为 $[s, \underline{1}, 0, i]$，$1 \le 1$，Koa 没有溺水。 - $t = 2$ 时 Koa 游到 $x = 2$，$t = 3$ 时海滩为 $[s, 2, \underline{1}, i]$，$1 \le 1$，Koa 没有溺水。 - $t = 3$ 时 Koa 游到 $x = 3$，$t = 4$ 时海滩为 $[s, 1, 0, \underline{i}]$。 - $t = 4$ 时 Koa 到达小岛，成功！ 可以证明，在第 2 个测试用例中，Koa 无法到达小岛。 由 ChatGPT 4.1 翻译