题目详情题解（0）讨论（0）提交记录（0）

CF2152F.Triple Attack

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Zeus 正在分析战斗录像，以了解对手的攻击模式。对手有一个特殊能力：如果在 zz 时间内命中同一个目标三次，他的第三次攻击就会变得非常强力。

为了避免被对手触发强化攻击，Zeus 不能让对手在 zz 时间内连续命中三次。设 Y={y1,y2,…,ym}Y = \{y_1, y_2, \ldots, y_m\} 为包含 mm 个时间戳的多重集，每个 yiy_i 代表对手攻击命中的时刻。我们称 YY 是安全的，当且仅当对任意三个时间戳 {yi,yj,yk}\{y_i, y_j, y_k\}（1≤i<j<k≤m1 \le i < j < k \le m），都有 max⁡(yi,yj,yk)−min⁡(yi,yj,yk)>z\max(y_i, y_j, y_k) - \min(y_i, y_j, y_k) > z，其中 zz 是给定的时间窗口。

Zeus 有一个日志，记录了 nn 个时间戳 x1,x2,…,xnx_1, x_2, \ldots, x_n，表示对手每次攻击命中的时间。所有时间戳按非递减顺序排列，即 xi≤xi+1x_i \le x_{i+1} 对所有 1≤i<n1 \le i < n 成立。

Zeus 有 qq 个关注的区间，每个区间为两个整数 1≤l≤r≤n1 \le l \le r \le n。对于每个区间，Zeus 想要知道在 [xl,xl+1,…,xr][x_l, x_{l+1}, \ldots, x_r] 中，最多能让多少次攻击通过，使得任何选出的集合都是安全的。

也就是说，Zeus 希望求出多重集 {xl,xl+1,…,xr}\{x_l, x_{l+1}, \ldots, x_r\} 的最大安全子集的大小。

输入格式

每个测试包含多组测试用例。第一行一个整数 tt 表示测试用例数（1≤t≤200001 \le t \le 20000）。接下来是每组测试用例的描述。

每组测试用例的第一行为两个整数 nn 和 zz（1≤n≤2500001 \le n \le 250000，1≤z≤1091 \le z \le 10^9）。

第二行为 nn 个整数 x1,x2,…,xnx_1, x_2, \ldots, x_n （1≤xi≤1091 \le x_i \le 10^9），表示对手攻击命中的时间戳，保证 xx 数组非递减。

第三行为一个整数 qq（1≤q≤2500001 \le q \le 250000）。

接下来的 qq 行，每行两个整数 ll 和 rr（1≤l≤r≤n1 \le l \le r \le n），表示区间的两端。

保证所有测试用例的 nn 之和不超过 250000250000，所有测试用例的 qq 之和不超过 250000250000。

输出格式

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

输入输出样例

  • 输入#1

    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

    输出#1

    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}\{1, 5, 7, 8, 11, 12\}，z=10z=10。子集 {1,5,12}\{1, 5, 12\} 是安全的，因为其唯一的三元组满足 12−1=11>1012-1=11>10。无法构造出大小为 44 的安全子集，所以本次询问的答案为 33。

在第二个测试用例的第一个询问，考虑时间戳 {1}\{1\}，z=1z=1。全体集合 {1}\{1\} 是安全的，因为没有任何三元组，因此答案为 11。

在第二个测试用例的第二个询问中，考虑时间戳 {1,1,1,3,3,3}\{1,1,1,3,3,3\}，z=1z=1。

子集 S={1,1,3,3}S = \{1,1,3,3\} 是安全的，因为：

  • 三元组 (i,j,k)=(1,2,3)(i,j,k) = (1,2,3)，max⁡(1,1,3)−min⁡(1,1,3)=2>1\max(1,1,3) - \min(1,1,3) = 2 > 1。
  • 三元组 (i,j,k)=(1,2,4)(i,j,k) = (1,2,4)，max⁡(1,1,3)−min⁡(1,1,3)=2>1\max(1,1,3) - \min(1,1,3) = 2 > 1。
  • 三元组 (i,j,k)=(1,3,4)(i,j,k) = (1,3,4)，max⁡(1,3,3)−min⁡(1,3,3)=2>1\max(1,3,3) - \min(1,3,3) = 2 > 1。
  • 三元组 (i,j,k)=(2,3,4)(i,j,k) = (2,3,4)，max⁡(1,3,3)−min⁡(1,3,3)=2>1\max(1,3,3) - \min(1,3,3) = 2 > 1。

无法构造大小为 55 的安全子集，所以本次询问的答案为 44。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页