题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$q$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，下标从$1$开始。

然后输入$q(1 \leq q \leq 10^5)$和$q$个询问，每个询问输入$L(1 \leq L \leq n)$和$k(1 \leq k \leq 10^9)$。

对于每个询问，输出最大的$R$，满足非空连续子数组$a[L]$~$a[R]$的AND$\geq k$。

如果不存在这样的$R$，输出$-1$。

输入样例

3
5
15 14 17 42 34
3
1 7
2 15
4 5
5
7 5 3 1 7
4
1 7
5 7
2 3
2 2
7
19 20 15 12 21 7 11
4
1 15
4 4
7 12
5 7

输出样例

2 -1 5 
1 5 2 2 
2 6 -1 5 

算法

$ST$表+二分答案

比较容易注意到按位与运算是具有单调性的，越与只可能越小或者不变。因此一旦$a[L] \lt k$肯定就无解了，输出$-1$。一般的情况就二分来确定最右的$R$，如果$a[L…R]$的AND$\geq k$，那么更小的$R$肯定也是满足的，可以往右搜索更大的$R$。

而在二分的过程中，我们需要快速求得子数组的按位与结果，可以预处理出一个按位与的$ST$表，这样就可以$O(1)$查询任意子数组的按位与结果。

复杂度分析

时间复杂度

预处理出$ST$表的时间复杂度为$O(nlog_2n)$。每个询问需要二分得到$R$，时间复杂度为$O(log_2n)$，$q$个询问的时间复杂度为$O(qlog_2n)$。整个算法的时间复杂度为$O((n+q)log_2n)$。

空间复杂度

$ST$表是整个算法的空间瓶颈，因此额外空间复杂度为$O(nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010, M = 20;
int T, n, q, a[N], st[N][M];

int query(int l, int r) {
    int k = log2(r - l + 1);
    return st[l][k] & st[r - (1<<k) + 1][k];
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for(int j = 0; j < M; j++) {
            for(int i = 1; i + (1 << j) - 1 <= n; i++) {
                if(!j) {
                    st[i][j] = a[i];
                }else {
                    st[i][j] = st[i][j - 1] & st[i + (1<<(j - 1))][j - 1];
                }
            }
        }
        scanf("%d", &q);
        while(q--) {
            int l, k;
            scanf("%d%d", &l, &k);
            if(a[l] < k) {
                printf("%d ", -1);
            }else {
                int left = l, right = n;
                while(left < right) {
                    int mid = left + right + 1 >> 1;
                    if(query(l, mid) >= k) {
                        left = mid;
                    }else {
                        right = mid - 1;
                    }
                }
                printf("%d ", right);
            }
        }
        puts("");
    }
    return 0;
}