\(Solution\)
比较典的题。
我们知道与运算的一个性质：对于任意自然数 \(x, y\) 都有 \(x\&y\leq\max(x,y)\)，读者可以自行证明，过程并不繁琐。
那么对于一段区间 \([l,r]\)，当 \(l\) 固定，\(r\) 不断变大时，\(f(l,r)\) 会呈单调不上升的趋势。
这就满足了二分的单调性。此时整个算法的复杂度在 \(\Theta(Tq\log n)\) 级别，而最后的步骤就是求 \(f(l,r)\)。
所以我们的问题变成了如何在 \(\Theta(\log n)\) 时间范围内求 \(f(l,r)\)，这是时限内能满足的最大时间。
这是典型的区间问题，很自然的想到 ST 表或是线段树。
那么问题得解。最终时间复杂度 \(\Theta(Tq\log^2 n)\)。
\(Code\)
#define int long long
const int N = 1e6 + 5;
namespace Jelly {
int n, q;
int tree[N << 2], a[N];
void Build(int x, int l, int r) {
if(l == r) {
tree[x] = a[l];
return ;
}
int mid = l + r >> 1;
Build(x << 1, l, mid);
Build(x << 1 | 1, mid + 1, r);
tree[x] = tree[x << 1] & tree[x << 1 | 1];
}
int Query(int l, int r, int x, int L, int R) {
if(r < L || l > R) return INT_MAX;
if(L <= l && r <= R) return tree[x];
int mid = l + r >> 1;
return Query(l, mid, x << 1, L, R) & Query(mid + 1, r, x << 1 | 1, L, R);
}
int main() {
Read(n);
for(int i = 1; i <= n; i ++) Read(a[i]);
Build(1, 1, n);
Read(q);
while(q --) {
int lft, k;
Read(lft, k);
int l = lft, r = n;
if(a[lft] < k) {
Write(-1, ' ');
continue;
}
while(l < r) {
int mid = l + r + 1 >> 1;
if(Query(1, n, 1, lft, mid) >= k) l = mid;
else r = mid - 1;
}
Write(l, ' ');
}
Writeln();
return 0;
}
}
signed main() {
int T = 1;
Read(T);
while(T --) Jelly::main();
return 0;
}