把每一项的数拆分成32位二进制,然后求前i项第j位二进制为1的前缀和,如果区间范围内的1等于区间范围,则是可行的,乘上对应位置的大小,每一位求和判断与k的大小
二分+前缀和
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int f[N][35],a[N];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 32; j++) {
f[i][j] = f[i - 1][j];
if ((a[i] >> j) & 1) f[i][j]++;
}
}
int q,l,k;
cin >> q;
while (q--) {
cin >> l >> k;
auto check = [&](int r) {
int x=0;
for (int i = 0; i < 32; i++) {
int p = f[r][i] - f[l - 1][i];
if (p == r - l + 1) x += 1 << i;
}
return x >= k;
};
int l1 = l-1 ;int r=n+1;
while (l1 +1 < r) {
int mid = l1 + r >> 1;
if (check(mid)) {
l1 = mid;
}
else r = mid;
}
if (l1 == l - 1) cout << -1 << ' ';
else cout << l1 << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}