Binary search + ex
bh1234666
·
·
题解
看到这题第一反应可能是贪心，二分时每次使区间最小，但是这样做是不正确的。因为直接贪心时靠前的操作权值^*小，靠后的操作权值大，靠前的决策会影响靠后的决策，即权值小的决策影响权值大的决策，显然不正确。
例如对于 $n=13$，查询序列的第 $5$ 个（下标为 $4$，接下来的位置均指下标）。直接贪心过程为：
$$
[0,12] \stackrel{w=1}{\longrightarrow} [0,5] \stackrel{w=0}{\longrightarrow} [3,5] \stackrel{w=1}{\longrightarrow} [4,5] \stackrel{w=0}{\longrightarrow} [4,4]
$$
但实际上有更优解法：
$$
[0,12] \stackrel{w=0}{\longrightarrow} [0,6]\stackrel{w=0}{\longrightarrow}[4,6] \stackrel{w=1}{\longrightarrow} [4,4]
$$
第一步贪心看似比最优解短了 $1$ ,贪心的下一步使得查找的值出现在了中部，导致 $ [3,5] \stackrel{w=1}{\longrightarrow} [4,5]$ 这一步无法使得长度折半。而贪心前面短的那一步最优解在下一步除二时除掉了，而在更靠后的 $[4,6] \stackrel{w=1}{\longrightarrow} [4,4]$ 比贪心短了 $1$。
对于 $\text{sub2}$ ，发现每次 $w$ 的值不会影响答案，直接输出 $\log_2 n$ 即可。
发现询问次数只有 $100$ 次，直接暴力。为便于实现，可以采用递归实现的二分，每次递归时分两类递归取最小即可。
由于递归层数为 $\log_2 n$ 层，每层分两种情况，最终复杂度为 $O(nq)$，可以通过此题。
核心代码：
```
int find(int k,int f,int l)
{
if(f==l) return 0;
int mid=(f+l)>>1,ret=32;
if(mid<k) ret=find(k,mid+1,l);
else ret=find(k,f,mid);
mid=(f+l+1)>>1;
if(mid<=k) ret=min(ret,find(k,mid,l));
else ret=min(ret,find(k,f,mid-1));
return ret+1;
}
int main()
{
int i,n,q,k;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",num+i);
scanf("%d",&q);
while(q--)
{
scanf("%d",&k);
for(i=0;i<n;i++)
if(num[i]==k) break;
printf("%d\n",find(i,0,n-1));
}
return 0;
}
```
### extra:
对于给定的 $n$，考虑查找第 $0\sim n-1$ 下标时所需要的次数。
显然次数只能为 $\lfloor \log n\rfloor\sim \lfloor \log n\rfloor +1$。
写出 $n$ 的二进制，设高位连续的 $1$ 的数量为 $t$，低位连续的 $0$ 的数量为 $k$。
当 $n$ 为偶数时 $w$ 不会影响二分下一步的情况，因此显然存在 $2^k$ 个循环节。
考虑每次操作对区间长度 $len$ 的影响，每次操作的实质是：
当 $len_i$ 为偶数时，$len_{i+1}=\lfloor \dfrac{len_i}{2}\rfloor$。
当 $len_i$ 为奇数时，若查找的数不在序列正中间，则可以选择 $len_{i+1}=\lfloor \dfrac{len_i}{2}\rfloor$ 或者 $\lfloor \dfrac{len_i}{2}\rfloor+1$，若查找的数在正中间则 $len_{i+1}=\lfloor \dfrac{len_i}{2}\rfloor+1$。
显然要被查找的数不会连续两次出现在正中间，因此必然可以通过某种操作使得所处位最高的 $0$(指 $len$ 在二进制下，下同) 不产生进位。也就是说单个循环节内的答案只与开头连续的 $1$ 有关，显然对于连续的 $1$，会间隔出现不进位和进位的情况。
注意，虽然最高位的 $0$ 可以使得处理到 $1$ 时长度一定，但是查询的数在序列中的相对位置会受到低位的影响，因此循环节不会被高位的 $0$ 消除掉。
即循环节内部对称且中间部分为 $\lfloor \log n\rfloor$，开头结尾受到 $t$ 的影响会出现 $\lfloor \log n\rfloor$ 与 $\lfloor \log n\rfloor+1$ 相间的情况，长度为 $2^t-2$。
预处理循环节长度，得到询问在某个循环节的位置，判断是否在受到 $t$ 影响的区间及奇偶性（在 $\lfloor \log n\rfloor$ 与 $\lfloor \log n\rfloor+1$ 相间区间时）即可得到答案。
~~以上说明纯属扯淡，这个结论是我输出了 n 为 90 到 128 的结果以后观察得出的。~~
时间复杂度 $O(q)$。
核心代码:
```
int get_ans(int x)
{
if(n==1) return lgt;//lgt为[log n]
else
{
x%=len;//len为循环节长度，即n/2^k
if(x>len/2) x=len-x-1;
if(x>(1<<n)-2) return lgt;//此处的n为t
else if(x&1) return lgt+1;
else return lgt;
}
}
```
注意到会进行大量的取模运算，可以采用 barrett 约减优化取模，其原理是通过成本较低的乘法运算和位运算替换取模（整除）运算。
预处理 $brt=\lfloor 2^{r}/len\rfloor$，可以通过 $brt\times x /2^r$ 得到 $\lfloor x/len \rfloor$ 的近似值，当 $r$ 足够大时，得到的近似值与精确值至多差 $1$。
我们可以通过 $x-brt\times x /2^r$ 来得到 $x\bmod len$ 的近似值，若得到的值大于 $len$ 则减 $len$ 即可。
于是我们就通过两次减法一次乘法一次位运算（除二的幂次）和一次条件判断（上述运算的成本均远小于取模）替换掉了一次取模运算。
barrett 部分核心代码：
```
brt=((__uint128_t)1<<brtcnt)/len;//brt初始化
```
```
x=x-len*(unsigned long long)(brt*x>>brtcnt);
if(x>=len) x-=len;//等价于x%=len
```