P3641 [APIO2016] 最大差分

这是一道交互题

提交到Luogu上时，你的代码中需如下进行 findGap 和 MinMax 函数的声明：

extern "C" void MinMax(long long, long long, long long*, long long*);
extern "C" long long findGap(int, int);

有 \(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\)）中的最大值。

实现细节

你需要实现一个函数 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\) 分。

样例

考虑 \(N = 4, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 8\)。

则答案应该是 \(3\)，可以通过下面的几组对 MinMax 的询问获得：

调用 MinMax(1, 2, &mn, &mx)，则 mn 和 mx 皆返回 \(2\)。

调用 MinMax(3, 7, &mn, &mx)，则 mn 返回 \(3\)，mx 返回 \(6\)。

调用 MinMax(8, 9, &mn, &mx)，则 mn 和 mx 皆返回 \(8\)。

样例评测方式

样例测评系统从标准输入中读入两行。第一行包含两个整数，子任务编号 \(T\)，和序列长度 \(N\)。第二行包含 \(N\) 个严格递增的非负整数。然后该程序会向标准输出中写入两行，第一行为 findGap 的返回值，第二行为花费 \(M\) 的值。

下面的输入描述了上面的样例：

2 4
2 3 6 8

注意实际使用的交互库和 spj 对数据进行了加密。

限制与约定

对于所有的测试点，有 \(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 分，否则将得到 \(\frac{60}{\sqrt{\frac MN + 1} - 1}\) 分。你的该子任务的得分是其下所有测试点中的最低分。

解析

子任务一（30 pts）

这一部分很简单，只需要询问 \((a_1, a_n)\) 的值，然后依次询问 \((a_2, a_{n - 1}), (a_3, a_{n - 2}), \ldots\) 即可

子任务二（70 pts）

我们这次还是先问出 \(a_1\) 和 \(a_n\)，然后考虑一下答案的最小值，就是中间 \(n - 2\) 个数均匀分配。

这时答案最小是 \(\frac{a_n - a_1}{n - 1}\)，如果把序列分块，每块大小是 \(\frac{a_n - a_1}{n - 1}\) 的话，很显然块内不会有答案。

那么我们就可以把每个块都问一遍，答案只会出现在当前块的最小值和上一个有值的块的最大值。

实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
extern "C" void MinMax(ll, ll, ll *, ll *);
extern "C" ll findGap(int, int);
namespace subtaskA
{
    const int MAXN = 1e5 + 10;
    ll a[MAXN], ans;
    ll findGap(int n)
    {
        MinMax(0, 1e18, a + 1, a + n);
        for (int l = 2, r = n - 1; l <= r; l++, r--)
            MinMax(a[l - 1] + 1, a[r + 1] - 1, a + l, a + r);
        for (int i = 1; i < n; i++)
            ans = max(ans, a[i + 1] - a[i]);
        return ans;
    }
} // namespace subtaskA
namespace subtaskB
{
    ll L, R, mn, mx, len, block, lst, ans;
    ll findGap(int n)
    {
        MinMax(0, 1e18, &L, &R);
        len = (R - L + 1);
        block = len / (n - 1);
        if (len % (n - 1))
            block++;
        lst = L;
        for (ll l = L + 1; l < R; l += block)
        {
            ll r = min(l + block - 1, R - 1);
            MinMax(l, r, &mn, &mx);
            ans = max(ans, mn - lst);
            if (mx > 0)
                lst = mx;
        }
        ans = max(ans, R - lst);
        return ans;
    }
} // namespace subtaskB
ll findGap(int T, int n)
{
    if (T == 1)
        return subtaskA::findGap(n);
    else
        return subtaskB::findGap(n);
}