CF2152F Triple Attack

Zeus 正在分析战斗录像，以了解对手的攻击模式。对手有一个特殊能力：如果在 $z$ 时间内命中同一个目标三次，他的第三次攻击就会变得非常强力。 为了避免被对手触发强化攻击，Zeus 不能让对手在 $z$ 时间内连续命中三次。设 $Y = \{y_1, y_2, \ldots, y_m\}$ 为包含 $m$ 个时间戳的多重集，每个 $y_i$ 代表对手攻击命中的时刻。我们称 $Y$ 是安全的，当且仅当对任意三个时间戳 $\{y_i, y_j, y_k\}$（$1 \le i < j < k \le m$），都有 $\max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) > z$，其中 $z$ 是给定的时间窗口。 Zeus 有一个日志，记录了 $n$ 个时间戳 $x_1, x_2, \ldots, x_n$，表示对手每次攻击命中的时间。所有时间戳按非递减顺序排列，即 $x_i \le x_{i+1}$ 对所有 $1 \le i < n$ 成立。 Zeus 有 $q$ 个关注的区间，每个区间为两个整数 $1 \le l \le r \le n$。对于每个区间，Zeus 想要知道在 $[x_l, x_{l+1}, \ldots, x_r]$ 中，最多能让多少次攻击通过，使得任何选出的集合都是安全的。 也就是说，Zeus 希望求出多重集 $\{x_l, x_{l+1}, \ldots, x_r\}$ 的最大安全子集的大小。

每个测试包含多组测试用例。第一行一个整数 $t$ 表示测试用例数（$1 \le t \le 20000$）。接下来是每组测试用例的描述。 每组测试用例的第一行为两个整数 $n$ 和 $z$（$1 \le n \le 250000$，$1 \le z \le 10^9$）。 第二行为 $n$ 个整数 $x_1, x_2, \ldots, x_n$ （$1 \le x_i \le 10^9$），表示对手攻击命中的时间戳，保证 $x$ 数组非递减。 第三行为一个整数 $q$（$1 \le q \le 250000$）。 接下来的 $q$ 行，每行两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示区间的两端。 保证所有测试用例的 $n$ 之和不超过 $250000$，所有测试用例的 $q$ 之和不超过 $250000$。

对于每组测试用例的每个询问，输出一个整数，表示指定区间内所能选出的最大安全子集的大小。

在第一个测试用例的第一个询问中，考虑时间戳 $\{1, 5, 7, 8, 11, 12\}$，$z=10$。子集 $\{1, 5, 12\}$ 是安全的，因为其唯一的三元组满足 $12-1=11>10$。无法构造出大小为 $4$ 的安全子集，所以本次询问的答案为 $3$。 在第二个测试用例的第一个询问，考虑时间戳 $\{1\}$，$z=1$。全体集合 $\{1\}$ 是安全的，因为没有任何三元组，因此答案为 $1$。 在第二个测试用例的第二个询问中，考虑时间戳 $\{1,1,1,3,3,3\}$，$z=1$。 子集 $S = \{1,1,3,3\}$ 是安全的，因为： - 三元组 $(i,j,k) = (1,2,3)$，$\max(1,1,3) - \min(1,1,3) = 2 > 1$。 - 三元组 $(i,j,k) = (1,2,4)$，$\max(1,1,3) - \min(1,1,3) = 2 > 1$。 - 三元组 $(i,j,k) = (1,3,4)$，$\max(1,3,3) - \min(1,3,3) = 2 > 1$。 - 三元组 $(i,j,k) = (2,3,4)$，$\max(1,3,3) - \min(1,3,3) = 2 > 1$。 无法构造大小为 $5$ 的安全子集，所以本次询问的答案为 $4$。 由 ChatGPT 5 翻译