Luogu

LOJ

UOJ

分析

Subtask1

首先调用 MinMax(0,1e18,&a[1],&a[n]) 来求出 $a_1$ 和 $a_n$。

然后不断调用 MinMax(a[i-1]+1,a[j+1]-1,&a[i],&a[j]) 即可求出整个序列。

Subtask2

首先调用 MinMax(0,1e18,&a[1],&a[n]) 来求出 $a_1$ 和 $a_n$。

设 $B=\lceil\frac{a_n-a_1}{n-1}\rceil$，则答案至少为 $B$。如果我们把值域按 $B$ 分块，则每一块内一定不会出答案。

于是答案只可能是这一块的最小值减去上一块的最大值，逐块处理一下即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#include "gap.h"
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

const int N=100000+10;

ll a[N];

ll findGap(int T,int n) {
    if (T==1) {
        a[0]=-1,a[n+1]=2e18;
        for (int i=1,j=n;i<=j;++i,--j)
            MinMax(a[i-1]+1,a[j+1]-1,&a[i],&a[j]);
        ll ans=0;
        for (int i=1;i<n;++i) ans=max(ans,a[i+1]-a[i]);
        return ans;
    } else {
        MinMax(0,2e18,&a[1],&a[n]);
        ll B=ceil(1.0*(a[n]-a[1])/(n-1)),lst=a[1],ans=0;
        for (ll l=a[1]+1;l<=a[n]-1;l+=B) {
            ll r=min(l+B-1,a[n]-1);
            ll x,y; MinMax(l,r,&x,&y);
            if (~x) ans=max(ans,x-lst),lst=y;
        }
        ans=max(ans,a[n]-lst);
        return ans;
    }
}