题解
第一个子任务直接询问最大最小，每次可以问出来两个，再最大最小-1再问两个，最多问\(\frac{N + 1}{2}\)次就还原出了序列
第二个子任务由于差分肯定会大于等于\(\lceil \frac{mx - mn}{N - 1} \rceil\)
那么我们直接把序列最大最小按照这个值分块，只用两个块之间的差分大小来更新答案
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 1000005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
void MinMax(int64 s,int64 t,int64 &mn,int64 &mx) {
putchar('?');space;out(s);space;out(t);enter;
fflush(stdout);
read(mn);read(mx);
}
int64 inf = 1e18;
int64 findGap(int T,int N) {
int64 mn,mx;
int64 ans = 0;
if(T == 1) {
MinMax(0,inf,mn,mx);
int64 ls = mn,lt = mx;
for(int i = 1 ; i <= (N + 1) / 2 - 1 ; ++i) {
if(ls + 1 > lt - 1) break;
MinMax(ls + 1,lt - 1,mn,mx);
if(mn == -1) break;
ans = max(mn - ls,ans);
ans = max(lt - mx,ans);
ls = mn,lt = mx;
}
ans = max(ans,lt - ls);
}
else {
MinMax(0,inf,mn,mx);
int64 len = (mx - mn - 1) / (N - 1) + 1;
int64 a = mn,m2 = mx;
int64 pre = mn;
ans = len;
for(int i = 1 ; i <= N - 1 ; ++i) {
int64 b;
b = min(a + len,m2);
MinMax(a,b,mn,mx);
if(mn != -1) {
ans = max(ans,mn - pre);
pre = mx;
}
if(a > m2 - len - 1) break;
a = a + len + 1;
}
}
return ans;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
int T,N;
read(T);read(N);
int64 x = findGap(T,N);
putchar('!');space;out(x);enter;fflush(stdout);
return 0;
}