http://uoj.ac/problem/206

对于T=1，直接从两端往中间跳可以遍历所有的点。

对于T=2，先求出最小值a和最大值b，由鸽巢原理，答案一定不小于\(\frac{b-a}{N-1}\)。

这样设\(L=\frac{b-a}{N-1}\)上取整，对\([a,b]\)分块，块大小为\(L-1\)，在块之间查询答案，因为块内的答案都\(\leq L-1\)。

能在3N次内求出。

好神啊。

#include "gap.h"

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll findGap(int T, int N) {

	if (T == 1) {

		ll ans = 0, a, b, c, d;

		MinMax(0, 1000000000000000000ll, &a, &b);

		for (int cnt = 2; cnt << 1 <= N + 1; ++cnt) {

			MinMax(a + 1, b - 1, &c, &d);

			ans = max(ans, max(c - a, b - d));

			a = c; b = d;

		}

		return max(ans, b - a);

	} else {

		ll a, b, c, d, L, ans;

		MinMax(0, 1000000000000000000ll, &a, &b);

		L = (b - a) / (N - 1); if ((N - 1) * L < b - a) ++L; ans = L;

		ll tmp = a;

		for (; tmp < b; tmp += L) {

			MinMax(tmp, tmp + L - 1, &c, &d);

			if (c != -1) {

				ans = max(ans, c - a);

				a = d;

			}

		}

		return max(ans, b - a);

	}

}