风眼定位

【题意简述】

存在一个长度为 $n$、元素互不相同的隐藏序列。调用 $\operatorname{Query}(l,r)$ 可以得到区间 $[l,r]$ 中次大元素在原序列中的位置。要求在不超过 $40$ 次询问内返回全局最大元素的位置。

【Hint】

【提示】

先询问整个区间得到全局次大值的位置 $s$。只要后续询问区间同时包含 $s$ 与全局最大值，返回值就一定仍为 $s$。

【数据点 111】

当 $n\leq 20$ 时，先询问整个区间得到全局次大值位置 $s$，再逐步缩短包含 $s$ 的区间，排除不可能成为最大值的位置。即使线性缩短区间，询问次数也不会超过 $20$。

这一档已经给出最重要的判断：若某个询问区间包含 $s$，那么返回 $s$ 当且仅当这个区间也包含全局最大值。

【数据点 222】

特殊性质保证最大值位于端点。询问 $[1,n]$ 得到 $s$ 后，最大值只可能在 $1$ 或 $n$。若询问 $[1,s]$ 返回 $s$，说明最大值在左侧，答案为 $1$；否则答案为 $n$。

【正解】

首先询问 $[1,n]$，记返回位置为 $s$。若 $s=1$，最大值只能位于右侧；若 $s=n$，最大值只能位于左侧。

当 $1<s<n$ 时，询问 $[1,s]$。若返回 $s$，则区间中同时包含全局最大值与全局次大值，最大值位于 $s$ 左侧；否则最大值位于 $s$ 右侧。

接下来只需要在已经确定的一侧二分，并保证每次询问都包含 $s$。

【最大值位于左侧】

维护答案属于 $[l,r]\subseteq[1,s-1]$。取上中点

并询问 $[m,s]$。

• 若返回 $s$，说明最大值位于 $[m,s-1]$，令 $l=m$；
• 否则最大值位于 $[l,m-1]$，令 $r=m-1$。

【最大值位于右侧】

维护答案属于 $[l,r]\subseteq[s+1,n]$。取下中点

并询问 $[s,m]$。

• 若返回 $s$，说明最大值位于 $[s+1,m]$，令 $r=m$；
• 否则最大值位于 $[m+1,r]$，令 $l=m+1$。

两种二分都始终保留真实答案，并严格缩短区间，所以最终 $l=r$ 时得到全局最大值位置。

【询问次数】

第一次询问得到 $s$，至多再用一次询问判断方向。二分长度不超过 $n-1$，所以总询问次数不超过

当 $n\leq 10^5$ 时，这个数量远小于 $40$。额外空间复杂度为 $\mathcal{O}(1)$。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/304Name:locate.cpp5You steal,I kill.6*/7#include "locate.h"8using namespace std;9 10void Init(int c,int T){11    return;12}13 14int Locate(int c,int n){15    int Second=Query(1,n);16    bool Left;17    if(Second==1) Left=false;18    else if(Second==n) Left=true;19    else Left=(Query(1,Second)==Second);20    if(Left){21        int l=1,r=Second-1;22        while(l<r){23            int Mid=(l+r+1)>>1;24            if(Query(Mid,Second)==Second) l=Mid;25            else r=Mid-1;26        }27        return l;28    }29    int l=Second+1,r=n;30    while(l<r){31        int Mid=(l+r)>>1;32        if(Query(Second,Mid)==Second) r=Mid;33        else l=Mid+1;34    }35    return l;36}