#4759. IOI 2022. 无线电信号塔(towers)

IOI 2022. 无线电信号塔(towers)

无线电信号塔(towers)

雅加达有 NN 个无线电信号塔。这些信号塔排布成一条直线,并且从左到右依次编号为从 00N1N - 1。 对于每个满足 0iN10 \le i \le N - 1ii,信号塔 ii 的高度为 H[i]H[i] 米。 所有塔的高度都是不同的

对于某个为正数的信号干扰参数 δ\delta,一对信号塔 iijj (0i<jN10 \le i \lt j \le N - 1) 之间能够互相通信,当且仅当存在一个中间信号塔 kk 满足如下条件:

  • ii 在塔 kk 的左边,并且塔 jj 在塔 kk 的右边,即 i<k<ji \lt k \lt j
  • ii 和塔 jj 的高度都至多为 H[k]δH[k] - \delta 米。

Pak Dengklek 想租一些信号塔来组建他的新无线电网络。 你的任务是回答 Pak Dengklek 提出的 QQ 个询问。这些询问的形式如下: 给定参数 L,RL, RDD (0LRN10 \le L \le R \le N - 1D>0D > 0),在满足下述所有条件时,Pak Dengklek 最多能够租多少个信号塔:

  • Pak Dengklek 只能租编号在 LLRR 之间的信号塔(包括 LLRR);
  • 信号干扰参数 δ\delta 的值为 DD
  • Pak Dengklek 租的信号塔两两之间必须能够进行通信。

注意,无论中间信号塔 kk 是否被租,两个已租的信号塔都可以借助信号塔 kk 进行通信。

实现细节

你需要实现以下函数:

void init(int N, int[] H)
  • NN: 信号塔的数量。
  • HH: 一个长度为 NN 的数组,给出信号塔的高度。
  • 这个函数恰好被调用一次,且在函数 max_towers 的所有调用之前。
int max_towers(int L, int R, int D)
  • LL, RR:信号塔编号区间的边界。
  • DD:信号干扰参数 δ\delta 的值。
  • 该函数应返回 Pak Dengklek 最多能租的信号塔数量(用于组建信号网络),这里 Pak Dengklek 只能租 LLRR之间(包含 LLRR)的信号塔,且信号干扰参数 δ\delta 的值是 DD
  • 该函数将被调用恰好 QQ 次。

例子

考虑如下函数调用序列:

init(7, [10, 20, 60, 40, 50, 30, 70])
max_towers(1, 5, 10)

Pak Dengklek 可以租编号为 11, 3355 的信号塔。 下面给出了这个例子的示意图,其中的灰色梯形表示被租的信号塔。

信号塔 3355 可以借助信号塔 44 进行通信,这是因为 40501040 \le 50 - 1030501030 \le 50 - 10。 信号塔 1133 可以借助信号塔 22 进行通信。 信号塔 1155 可以借助信号塔 33 进行通信。 无法租超过 33 个信号塔,因此函数应返回 33

max_towers(2, 2, 100)

在这个区间里只有 11 个信号塔,所以 Pak Dengklek 只能租借 11 个信号塔。 因此函数应返回 11

max_towers(0, 6, 17)

Pak Dengklek 可以租信号塔1133 。 信号塔 1133 可以借助信号塔 22进行通信,这是因为 20601720 \le 60 - 1740601740 \le 60 - 17。 无法租赁超过 22 个信号塔,因此函数应返回 22

约束条件

  • 1N100  0001 \le N \le 100\;000
  • 1Q100  0001 \le Q \le 100\;000
  • 1H[i]1091 \le H[i] \le 10^9 (对于所有满足 0iN10 \le i \le N - 1ii )
  • H[i]H[j]H[i] \ne H[j] (对于所有满足 0i<jN10 \le i \lt j \le N - 1iijj )
  • 0LRN10 \le L \le R \le N - 1
  • 1D1091 \le D \le 10^9

子任务

  1. (4 分) 存在一个满足下述所有条件的信号塔 kk (0kN10 \le k \le N - 1)
    • 对于 0ik10 \le i \le k - 1的每个iiH[i]<H[i+1]H[i] \lt H[i + 1]
    • 对于 kiN2k \le i \le N - 2的每个iiH[i]>H[i+1]H[i] \gt H[i + 1]
  2. (11 分) Q=1Q = 1N2000N \le 2000
  3. (12 分) Q=1Q = 1
  4. (14 分) D=1D = 1
  5. (17 分) L=0L = 0R=N1R = N - 1
  6. (19 分) DD 的值在 max_towers 的所有调用中都是相同的
  7. (23 分) 没有额外的限制

评测程序示例

评测程序示例读取如下格式的输入:

  • 11 行:N  QN \; Q
  • 22 行:H[0]  H[1]    H[N1]H[0] \; H[1] \; \ldots \; H[N - 1]
  • 3+j3 + j 行(0jQ10 \le j \le Q - 1):L  R  DL \; R \; D(对应第 jj 次询问)

评测程序示例按照如下的格式打印你的答案:

  • 1+j1 + j 行(0jQ10 \le j \le Q - 1):max_towers 对第 jj 次询问的返回值