E
题意:
由n个元素组成的数组a。我们定义f(l,r)=al & al+1 &…& ar(这里&表示位与操作)。
请注意,当l>r时,f(l,r)是没有定义的。q次查询,每个查询包含两个数字k和l,
找到最大的索引r(l≤r≤n),使得f(l,r)≥k。
越&数越小
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int id[N][35], sum[N][35];
bool check(int l, int r, int k)
{
int x = a[l];
for(int i = 0; i <= 31; i ++)
{
if((x >> i & 1) && (sum[r][i] - sum[l - 1][i] >= 1))
//如果说该位是1,且[l,r]中这个位子上有0的存在,就让x的这个位子上为0,
//因为在这个区间里面,只要有一个0,就会全部变成1
//然后再比较x和k
{
x -= 1 << i;
if(x < k) return false;
}
}
return true;
}
void solved()
{
int n; cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= 31; j ++)
id[i][j] = 0; //初始化
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= 31; j ++)
if(!(a[i] >> j & 1))
id[i][j] = 1; //记录每个数的这个位子是不是0
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= 31; j ++)
sum[i][j] = sum[i - 1][j] + id[i][j]; //前缀和,记录该位上0的个数
int q; cin >> q;
while(q --)
{
int l, k; cin >> l >> k;
if(a[l] < k)
{
cout << "-1" << " ";
continue;
}
int a = l, b = n;
while(a < b) //用二分找到最大r
{
int mid = (a + b + 1) >> 1;
if(check(l, mid, k)) a = mid;
else b = mid - 1;
}
cout << a << " ";
}
cout << endl;
}
int main()
{
int t; cin >> t;
while(t --)
solved();
return 0;
}