P3641 [APIO2016] 最大差分

## 评测方式 以下是本题评测方式，与题面不符时以这里为准。 你的代码中不应该包含 `gap.h` 库。 你的代码中需如下进行 `findGap` 和 `MinMax` 函数的声明： ```cpp extern "C" void MinMax(long long,long long,long long*,long long*); extern "C" long long findGap(int,int); ``` [spj 与交互库](https://www.luogu.com.cn/paste/c4olee2x) 不保证没锅，要是有锅请私信供题人然后 D 死他。

有 $N$ 个严格递增的非负整数 $a_1, a_2, \dots, a_N$（$0 \leq a_1 < a_2 < \cdots < a_N \leq 10^{18}$）。你需要找出 $a_{i + 1} - a_i$（$1 \leq i \leq N - 1$）里的最大的值。 你的程序不能直接读入这个整数序列，但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节，请根据你所使用的语言，参考下面的实现细节部分。 你需要实现一个函数,该函数返回 $a_{i + 1} - a_i$（$1 \leq i \leq N - 1$）中的最大值。 ## 实现细节 **本题只支持 C++（包括 cpp11，cpp14，cpp17）**。 ### C/C++ 你需要包含头文件 `gap.h`。 你需要实现一个函数 `findGap(T, N)`，该函数接受下面的参数，并返回一个 `long long` 类型的整数： - $T$：子任务的编号（$1$ 或者 $2$） - $N$：序列的长度 你的函数 `findGap` 可以调用系统提供的查询函数 `MinMax(s, t, &mn, &mx)`，该函数的前两个参数 $s$ 和 $t$ 是 `long long` 类型的整数，后两个参数 `&mn` 和 `&mx` 是 `long long` 类型的整数的指针（`mn` 和 `mx` 是 `long long` 类型的整数）。当 `MinMax(s, t, &mn, &mx)` 返回时，变量 `mn` 将会存储满足 $a_i \in [s, t]$ 中 $a_i$ 的最小值，变量 `mx` 将会存储满足 $a_i \in [s, t]$，$a_i$ 的最大值。如果区间 $[s, t]$ 中没有序列中的数，则 `mn` 和 `mx` 都将存储 $-1$。在查询时需要满足 $s \leq t$，否则程序将会终止，该测试点计为 $0$ 分。 ### Pascal 你需要使用单元 `graderhelperlib`。 你需要实现一个函数 `findGap(T, N)`，该函数接受下面的参数，并返回一个 `Int64` 类型的整数： - $T$：子任务的编号（$1$ 或者 $2$）（`Integer` 类型） - $N$：序列的长度（`LongInt` 类型） 你的函数 `findGap` 可以调用系统提供的查询函数 `MinMax(s, t, mn, mx)`，该函数的前两个参数 $s$ 和 $t$ 是 `Int64` 类型的整数，后两个参数 `mn` 和 `mx` 是传引用方式的 `Int64` 类型的整数（过程内部对这两个变量的修改会影响到外部的对应变量的值）。当 `MinMax(s, t, mn, mx)` 执行完毕时，变量 `mn` 将会存储满足 $a_i \in [s, t]$ 中 $a_i$ 的最小值，变量 `mx` 将会存储满足 $a_i \in [s, t]$，$a_i$ 的最大值。如果区间 $[s, t]$ 中没有序列中的数，则 `mn` 和 `mx` 都将存储 $-1$。在查询时需要满足 $s \leq t$，否则程序将会终止，该测试点计为 $0$ 分。

无

无

## 限制与约定 对于所有的测试点，有 $2 \leq N \leq 100000$。 每一个测试点开始测试之前，$M$ 都将被初始化为 $0$。 子任务 1（$30$ 分）：每一次调用 `MinMax` 都将使 $M$ 加 $1$。为了获得所有分数，需要满足对于该子任务下的所有测试点，都有 $M \leq \frac{N + 1}{2}$。 子任务 2（$70$ 分）：定义 $k$ 为调用 `MinMax` 时，区间 $[s, t]$ 中的序列中数的数量。每次调用 `MinMax`，将使 $M$ 加上 $k + 1$。对于每一个测试点，如果 $M \leq 3N$，你将得到 70 分，否则将得到 $\dfrac{60}{\sqrt{\frac MN + 1} - 1}$ 分。你的该子任务的得分是其下所有测试点中的最低分。