这题我想到了个大概，按位与的话结果肯定是递减的，而且要从二进制每一位下手，但是思路只停留在暴力对整个数操作。
当然，利用这个性质，肯定要二分。
拆位思想
比如要计算
1110001
1101110
0100010
我们知道最后结果肯定是留下都有 \(1\) 的位
0100000
但每次都进行按位与肯定是超时的，能不能把按位与和前缀和两个思想结合应用呢？
对于上述的式子，我们可以拆位分析，具体地：
- 对于三个按位与的七位二进制数，预处理出第 \(k(k \leq 7)\) 位在前 \(i(i\leq 3)\) 数中的数码\((0/1)\) 的前缀和。
- 那么显然判断结果时，只要按位查询前缀和，等于三的就是 \(1\)，否则是 \(0\)。
推广到 \(n\) 个 \(m\) 位的二进制数：
- 维护一个前缀和数组 \(pref_{i, j}\) 表示前 \(i\) 个数，第 \(j\) 个数码的前缀和。
- 如果第 \(i\) 个数的第 \(j\) 个数码是 \(1\)，那么 \(pref_{i + 1, j} = pref_{i, j} + 1\)
- 如果第 \(i\) 个数的第 \(j\) 个数码是 \(0\)，那么 \(pref_{i + 1, j} = pref_{i, j}\)
- 查询这个数的按位与/乃至按位或这种跟 \(1/0\) 个数很相关的，就可以利用预处理出来的前缀和 \(O(1)\) 查询。
- 对于本题，显然前缀和等于数的间隔的位置的数码是 \(1\)，把这些数码再用 \(1<<j\) 加入总和，最后判断是否符合答案。
代码实现
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#define inf 0x7fffffff
#define endl '\n'
using namespace std;
using ll = long long;
void close_sync() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
const int N = 2e5 + 10;
const int bits = 30;
int pref[N][bits];
int a[N];
int n;
void bulidPrefix() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 30; j++) {
if (a[i] & (1 << j)) {//1 << j 即产生一个只有第 j 位是 1 的二进制数，进而与 a[i] 比较判断该位是否为 1
pref[i + 1][j] = pref[i][j] + 1;
}
else {
pref[i + 1][j] = pref[i][j];
}
}
}
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
bulidPrefix();
int q; cin >> q;
while (q--)
{
int l, k;
cin >> l >> k;
if (a[l - 1] < k) {cout << -1 << ' '; continue;}
int low = l, high = n;
int ans = l;
while(low <= high) {
int mid = low + (high - low >> 1);
int num = 0;
for (int j = 0; j < bits; j++) {
if (pref[mid][j] - pref[l - 1][j] == mid - l + 1) {//说明这 mid - l + 1 个数的 j 位有 mid - l + 1 个 1，即该位答案为 1
num += 1 << j;
}
}
if (num >= k) {
low = mid + 1;
ans = max(ans, mid);
}
else {
high = mid - 1;
}
}
cout << ans << ' ';
}
cout << endl;
}
int main() {
close_sync();
int _; std::cin >> _;
while(_--) solve();
return 0;
}