题目描述

难度分:$1300$

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

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(0 \leq a[i] \lt 2^{20})$。

输出最小的正整数$k$，使得$a$的所有长为$k$的连续子数组的OR都相同。注意答案是一定存在的，因为$k=n$一定满足要求。

输入样例

7
1
0
3
2 2 2
3
1 0 2
5
3 0 1 4 2
5
2 0 4 0 2
7
0 0 0 0 1 2 4
8
0 1 3 2 2 1 0 3

输出样例

1
1
3
4
4
7
3

算法

倍增+二分答案

先用倍增预处理出$ST$表，这样就可以$O(1)$查询任意子数组的按位或结果。根据或运算越或越大（或者不变）的单调性，如果一个长度$k$可以使得所有长度为$k$的子数组按位或都相同，那么长度$\gt k$的子数组肯定也满足这个性质，所以二分这个最小长度，对于给定长度$len$，$O(n)$检查所有窗口的按位或结果：

1. 如果所有按位或的值都相等，这个长度就有可能是答案，记录这个长度并往左搜索看能不能更小。
2. 否则这个长度就太小了，应该往右搜索更大的长度。

复杂度分析

时间复杂度

倍增预处理的时间复杂度为$O(nlog_2n)$；二分的值域是$[1,n]$，$check$一次的时间复杂度为$O(n)$，所以二分答案的时间复杂度为$O(nlog_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈在于$ST$表，额外空间复杂度为$O(nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int T, n;
const int N = 100010, M = 18;
int 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];      // 根据查询信息的不同修改此处
}

void init() {
    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];
            }
        }
    }
}

bool check(int len) {
    int val = query(1, len);
    for(int r = len + 1; r <= n; r++) {
        int l = r - len + 1;
        if(query(l, r) != val) return false;
    }
    return true;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        init();
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(check(mid)) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        printf("%d\n", r);
    }
    return 0;
}