题解：CF1973D Cat, Fox and Maximum Array Split
g1ove
·
·
题解
题意
给出长度为 n 的数组和整数 k，定义 f(l, r) = (r - l + 1)\times\max_{x=l}^ra_x，询问是否存在一个最大值 m，使得把 a 数组分成 k 段后，使得每段 f(l,r)=m 都成立。若无解 m=-1。输出 m。
你可以询问交互库 2n 次，每次给出 l,x 两个参数，交互库会回答一个满足 f(l,r)=x 最小的 r。如果不存在 r，则交互库会回答 n+1。
注意，你并不知道 a 数组中的元素。
交互库询问格式：? l x
答案输出格式：! m
注意输出空行和刷新。
对于每次你输出的答案，如果正确，交互库会给出 1，错误则给出 -1。请使用一个变量存储这个输入。
## 思路
神秘交互题。
首先，题目只给了我们 $2n$ 次询问交互库的次数，这让我们只能往线性方面思考。
观察答案有什么特点，明显的，答案总有一个区间覆盖了 $m=\max_{x=1}^na_x$。
我们不妨往这个方向思考一番。根据 $m$ 总会被区间覆盖，而且长度不固定，不难得出 $ans$ 如果存在一定是 $m$ 的倍数。
现在我们缩小了答案的区间。
我们想想怎么得到 $m$。不难发现，$f(1,n)=m\times n$，是固定的。我们可以通过从小到大询问 $m\times n$ 来得到 $m$。最劣情况下，我们使用了 $n$ 次询问。
我们现在知道了答案的下界，那么能不能推个上界出来呢？
根据 $f$ 这个式子的优良性质，我们可以得到一个显然的结论：$f(l,r)\ge f(l,k)+f(k+1,r)$。
假设 $ans=t\times m$。
我们可以归纳得到：$ans\times k\le f(1,n)$。
然后变一下这个式子：$t\times m\times k\le n\times m$。
所以 $t\le \frac{n}{k}$。
现在做法已经很明显了。我们枚举每个 $m$ 的倍数，总共会枚举 $\frac{n}{k}$ 次，然后每次验证答案最多会询问 $k$ 次，最多询问 $n+\frac{n}{k}\times k=2n$ 次。在答案中取最大值即可，可以通过此题。
最后留给读者一个思考：其实如果存在答案的话，答案是唯一的。读者可以自己证明一下。
code
```cpp
#include<bits/stdc++.h>
#define ll long long
#define N 10005
using namespace std;
int n,k,m,res;
int g;
int main()
{
scanf("%d",&g);
while(g--)
{
scanf("%d%d",&n,&k);
for(int i=n;i>=1;i--)
{
int x;
printf("? %d %d\n",1,n*i);
fflush(stdout);
scanf("%d",&x);
if(x<=n)
{
m=i;
break;
}
}
res=0;
for(int i=1;i<=n/k;i++)
{
bool ok=1;
int lst=1;
for(int j=1;j<=k;j++)
{
if(lst>n)
{
ok=0;
break;
}
int x;
printf("? %d %d\n",lst,i*m);
fflush(stdout);
scanf("%d",&x);
lst=x+1;
}
if(lst!=n+1) ok=0;
if(ok)
{
res=1;
printf("! %d\n",i*m);
fflush(stdout);
break;
}
}
if(!res)
{
printf("! -1\n");
fflush(stdout);
}
scanf("%d",&res);
}
return 0;
}
```