【[APIO2016]最大差分】

第一道交互诶，不知道noi2019有没有交互。

传送门

子任务1（30分）

就是送的啊，会读题就会做。

先$MinMax(0,1e18,a_1,a_n)$你就知道了$a_1$和$a_n$，之后$MinMax(a_1+1,a_n-1,a_2,a_{n-1})$。。。。

这样问$\frac{n+1}{2}$次你就知道了整个序列。

子任务2（70分）

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

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

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

这样的话，第一次讯问对k的贡献是n+1，中间对k的贡献是$n-1+n-2$，意思是问了$n-1$次，出现了$n-2$个点。所以加起来最坏是$3n-2$。

#include "gap.h"
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll a[100011];
long long findGap(int T, int N){
    ll ans=0;int n=N;
if (T==1){
    a[0]=-1; a[n+1]=1LL*1000000000000000010;
    for (int i=1; i<=(n+1)>>1; i++)
        MinMax(a[i-1]+1,a[n-i+2]-1,&a[i],&a[n-i+1]);
    for (int i=1; i<n; i++)
        ans=max(ans,a[i+1]-a[i]);
}
else{
    ll minn,maxn,l,r,k,rl,las=-1;
    MinMax(0,1LL*1000000000000000000,&minn,&maxn);
    k=(maxn-minn)/(n-1); las=minn;
    if ((maxn-minn)%(n-1)) k++;
    for (ll i=minn+1; i<maxn; i+=k){
        rl=min(i+k-1,maxn-1);
        MinMax(i,rl,&l,&r);
        ans=max(ans,l-las);
        if (r>0) las=r;
    }
    ans=max(ans,maxn-las);
}
    return ans;
}