← 返回题目列表

Codeforces · 2152/F

F. 三重攻击

中文机器翻译题面 查看原题

Zeus 正在分析战斗重播以了解对手的攻击模式。对手具有特殊能力:如果他们在 $$$z$$$ 时间内对目标进行三次攻击,他们的第三次攻击将成为强大的增强攻击。

为了击败对手,宙斯不应该让对手触发强化攻击。令 $$$Y = \{y_1, y_2, \ldots, y_m\}$$$ 为 $$$m$$$ 时间戳的多重集,其中每个 $$$y_i$$$ 代表对手攻击落地的时间。我们称 $$$Y$$$ 为 安全 如果对于每三个时间戳 $$$\{y_i, y_j, y_k\}$$$ 使得 $$$1 \le i \lt j \lt k \le m$$$,则认为 $$$\max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) \gt z$$$,其中$$$z$$$ 是作为输入提供给您的时间范围的持续时间。

Zeus 有一个包含 $$$n$$$ 时间戳的日志,$$$x_1, x_2, \ldots, x_n$$$,代表对手攻击的时间。时间戳是 按非降序排序 。换句话说,$$$x_i \le x_{i+1}$$$ 对于所有$$$1 \le i \lt 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 20\,000$$$)。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$z$$$ ($$$1 \le n \le 250\,000$$$, $$$1 \le z \le 10^9$$$)。

第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$) — 对手攻击的时间戳。保证数组 $$$x$$$ 已排序,即 $$$x_i \le x_{i+1}$$$ 对于所有 $$$1 \le i \lt n$$$。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 250\,000$$$)。

接下来的 $$$q$$$ 行每行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) - 区间的端点。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$250\,000$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$250\,000$$$。

输出

对于每个 $$$q$$$ 查询,打印一个整数 - 给定间隔内攻击时间戳安全子集的最大大小。

示例

输入
复制

3
6 10
1 5 7 8 11 12
6
1 6
1 5
2 6
1 4
2 5
3 6
6 1
1 1 1 3 3 3
2
3 3
1 6
12 15
4 5 15 24 27 32 36 39 40 46 48 48
20
1 12
1 11
6 10
1 8
8 12
11 12
2 9
3 8
7 8
7 10
4 8
9 12
9 10
2 12
1 5
3 12
4 8
3 7
7 12
10 11

输出
复制

3
2
2
2
2
2
1
4
6
6
2
4
2
2
5
3
2
2
2
2
2
6
4
5
2
3
2
2

注意

在第一个测试用例的第一个查询中,我们考虑时间戳 $$$\{1, 5, 7, 8, 11, 12\}$$$ 和 $$$z=10$$$。子集 $$$\{1, 5, 12\}$$$ 是安全的,因为它唯一的三元组满足 $$$12 - 1 = 11 \gt 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 \gt 1$$$。
  • 对于三元组 $$$(i,j,k) = (1,2,4)$$$, $$$\max(1,1,3) - \min(1,1,3) = 2 \gt 1$$$。
  • 对于三元组 $$$(i,j,k) = (1,3,4)$$$, $$$\max(1,3,3) - \min(1,3,3) = 2 \gt 1$$$。
  • 对于三元组 $$$(i,j,k) = (2,3,4)$$$, $$$\max(1,3,3) - \min(1,3,3) = 2 \gt 1$$$。

不可能形成大小为 $$$5$$$ 的安全子集,因此此查询的答案是 $$$4$$$。