原题链接
思路：
开始变得奇怪了。
首先还是记pos为区间[1,n]的次大值位置。
然后再查询[1,pos]的次大值位置，如果等于pos的话，说明最大值在[1,pos]，否则说明最大值在[pos,n]。
然后再对这两部分进行二分查找，check的很巧妙。
假设最大值在[1,pos]，那么记mid为区间[l,r]的中点。查询的是 [mid,pos]的次大值位置，记作t。如果t==pos的话，说明最大值位置在[mid,r]里，反之，在[l,mid]里。
询问次数：2+log（1e5）
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7; int n; int ask(int l,int r){ if(l>=r) return -1; cout<<"? "<<l<<" "<<r<<endl; fflush(stdout); int pos;cin>>pos; return pos; } void solve(){ n=read; int pos=ask(1,n);//区间[1,n]的次大值 if(pos!=ask(1,pos)){///查询[1,pos]的次大值位置，不相等说明最大值在[pos,n] int l=pos,r=n,res; while(r-l>1){ int mid=(l+r)/2; if(pos==ask(pos,mid)) r=mid; else l=mid; } cout<<"! "<<r<<endl; } else{ int l=1,r=pos,res; while(r-l>1){ int mid=(l+r)/2; if(pos==ask(mid,pos)) l=mid; else r=mid; } cout<<"! "<<l<<endl; } } int main(){ int T=1; while(T--) solve(); return 0; }
