问题描述

塔子哥是一名魔法师，他有一个由 $n$ 个正整数组成的魔法序列 $A$。现在他想对这个序列施展魔法，每次施展魔法会给出三个正整数 $l,r,k$，塔子哥想知道在区间 $[l,r]$ 中是否存在一个位置 $i$，使得将区间 $[l,i]$ 中的所有数进行按位或运算的结果等于 $k$。如果存在，输出满足条件的最小的 $i$，否则输出 $-1$。

输入格式

思路

考虑对于每个查询，我们先二分找到最小的区间，满足 $k$ 中所有二进制位都存在，这个区间为 $[l, r_1]$

然后判断 $[l, r_1]$ 的区间或运算和是否为 $k$ 即可。

这里的二分中的 check 函数需要枚举 30 个二进制位。

所以我们需要先预处理出每个二进制位的前缀和，这样就可以 $O(1)$ 进行区间二进制位数量的查询。