题解：P14134 【MX-X22-T5】「TPOI-4E」Get MiN? Get MeX!
CuteLord
·
·
题解
简单题？
10pts
我们把 1\sim n 都扫一遍，其中会有两个值为 1 的位置，用 2 类询问判断一下就好了
25pts
首先我们不难发现，将一个序列从中间劈开，左右两边的 min+mex 的值是相等的，所以我们考虑维护两个区间，每次将每个区间砍半，询问这 4 个区间，我们发现必然有两个区间的值相等，且这两个值必然是 4 区间的值中的最小值，同时 0 和 1 在这两个区间内，证明不难留给读者自行思考。那么每次就可以将区间大小缩小一半，询问次数为 O(4\log_2 n)。最后找出两个值为 1 的点后用 10pts 的方法判断就好了。
40pts
容易想到 4 个区间中有一个询问是没有必要的，询问次数为 O(3\log_2 n)
100pts
我们这个 \log n 是降不下来的，于是考虑怎么每次用 2 次询问就可以缩小范围。假设当前的两个区间为 [l_1,r_1],[l_2,r_2]，他们询问出的值为 x，两个区间的中点为 m_1,m_2，区间 [l_1,m_1],(m_1,r_1],[l_2,m_2],(m_2,r_2] 询问出的值为 a,b,c,d， y=\min(a,b,c,d)，那么 y\le x。
同时我们有当 a=b 或 c=d 时 y<x,当 a=c 或 a=d 或 b=c 或 b=d 时 y=x。
证明不难。
由于 a=b 或者 c=d 同理，所以我们只考虑 a=b。
假设 0 在 [l_1,m_1] 区间内，那么 \min[l_1,m_1]=0 且 \operatorname{mex}[l_1,m_1]=a，此时由于 a=b 所以 \min (m_1,r_1]=a 且 \operatorname{mex}(m_1,r_1]=0。
我们发现，此时在区间 [l_1,r_1] 内 0 \sim a 都存在，那么 \min[l_1,r_1]=0 且 \operatorname{mex}[l_1,r_1]=a+1，即 x=a+1，也即 y<x。
由于 $a=c$ 或 $a=d$ 或 $b=c$ 或 $b=d$ 也同理，所以我们也只考虑 $a=c$。同样，我们假设 $0$ 在区间 $[l_1,m_1]$ 内，那么 $\min[l_1,m_1]=0$ 且 $\operatorname{mex}[l_1,m_1]=a$，此时由于 $a=c$ 所以 $\min[l_2,m_2]=a$ 且 $\operatorname{mex}[l_2,m_2]=0$。
我们知道，因为 $\min[l_2,m_2]=a$，所以 $a$ 一定在 $[l_2,m_2]$ 中，那么 $a$ 就一定不在 $(m_1,r_1]$ 中，因此 $\operatorname{mex}[l_1,r_1]$ 一定等于 $a$，同时根据 25pts 中的结论可以得到 $\min[l_2,r_2]=a$，此时 $x=a$，即 $x=y$。
$0$ 在 $[l_2,m_2]$ 区间内同理。
现在我们考虑询问出 $a,d$，那么有一下几种情况：
1. $a=d$：这个直接选 $a,d$；
2. $a>x,d>x$：直接选 $b,c$；
3. $a=x,d>x$：选择 $a,c$；
4. $a>x,d=x$：同理，选择 $b,d$；
5. $a<x$：选择 $a,b$；
6. $d<x$：同理，选择 $c,d$；
7. $a<x,d<x$：可以证明这种情况不存在。
由于区间每次会缩小一半，所以最多会缩小 $\log n$ 次，同时每次缩小使用 $2$ 次询问，加上开始时询问的一次，总共 $2 \log_2 n+1$ 次，在 $n \le 10^5$ 时最多为 $35$ 次。
最后当区间缩小为两个点时，两个点必然一个为 $1$ 一个为 $0$，直接用 10pts 的方法判断一下就做完了。
```c++
//by CuteLord uid:1114894
#include<bits/stdc++.h>
using namespace std;
int n;
int query(int l,int r,int op=0){
/*
询问就不给了
*/
}
int l1,r1;
int l2,r2;
int main(){
cin>>n;
l1=1,r1=n+1>>1;
l2=r1+1,r2=n;
int last=query(l1,r1);
while(1){
int m1=l1+r1>>1,m2=l2+r2>>1;
int a=query(l1,m1);
int b=query(m2+1,r2);
if(a==b){
r1=m1;
l2=m2+1;
last=a;
}else if(a>last&&b>last){
l1=m1+1;
r2=m2;
}else if(a<last){
l2=m1+1,r2=r1;
r1=m1;
last=a;
}else if(b<last){
l1=l2,r1=m2;
l2=m2+1;
last=b;
}else if(a==last&&b>last){
r1=m1;
r2=m2;
}else if(b==last&&a>last){
l1=m1+1;
l2=m2+1;
}
if(l1==r1&&l2==r2)break;
else if(l1==r1){
m2=l2+r2>>1;
a=query(l2,m2);
b=query(m2+1,r2);
if(a<b)r2=m2;
else l2=m2+1;
break;
}else if(l2==r2){
m1=l1+r1>>1;
a=query(l1,m1);
b=query(m1+1,r1);
if(a<b)r1=m1;
else l1=m1+1;
break;
}
}
if(query(l1,l1,1)<0)cout<<"! "<<l1;
else cout<<"! "<<l2;
}
```