题解

题目描述

小苯有一个长度为 n 的数组 a，他可以通过以下操作来改变数组：

• 对于每个 i，将 b[i] 设为 a[i] | a[(i+1)%n]，然后将 a 替换为 b。

要求找到最少需要多少次操作，使得数组 a 的最小值不小于 k。题目保证有解。

思路分析

该问题要求通过最少的操作使数组的最小值不小于k。每次操作将每个元素变为其与下一个元素的或。关键思路是每次操作扩展元素覆盖的连续区间，直到该区间的或结果不小于k。通过预处理稀疏表快速查询区间或，对每个元素二分查找满足条件的最小长度，所有元素中最大的所需操作次数即为答案。利用环状数组的双倍扩展处理循环，稀疏表优化查询效率，时间复杂度为O(n log n)。

1. 操作性质：每次操作后，每个元素变为原数组中相邻两个元素的或运算结果。经过多次操作后，每个元素的值实际上是原数组中连续多个元素的或结果。
2. 关键观察：要使得数组的最小值不小于 k，每个元素在若干次操作后必须覆盖足够的原数组元素，使得这些元素的或结果不小于 k。
3. 预处理：将原数组复制一次形成双倍数组，便于处理环状结构。
4. 稀疏表：使用稀疏表快速查询任意区间的或运算结果。
5. 二分查找：对每个元素，通过二分查找确定最少需要覆盖的连续元素个数，使得或结果不小于 k。

复杂度分析

• 预处理稀疏表：时间复杂度为 O(n log n)，空间复杂度为 O(n log n)。
• 二分查找：每个元素进行二分查找的时间复杂度为 O(log n)，总时间复杂度为 O(n log n)。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

// 构建稀疏表，用于快速查询区间或运算结果
vector<vector<int>> build_sparse_table(const vector<int>& a) {
    int n = a.size();
    int max_level = 0;
    while ((1 << max_level) <= n) max_level++; // 计算最大层数
    vector<vector<int>> st(max_level, vector<int>(n)); // 初始化稀疏表
    for (int i = 0; i < n; ++i) {
        st[0][i] = a[i]; // 第一层是原数组
    }
    for (int j = 1; j < max_level; ++j) {
        for (int i = 0; i + (1 << j) <= n; ++i) {
            // 区间或运算：st[j][i] = st[j-1][i] | st[j-1][i + (1 << (j-1))]
            st[j][i] = st[j-1][i] | st[j-1][i + (1 << (j-1))];
        }
    }
    return st;
}

// 预计算 log 表，用于快速计算区间长度对应的 log 值
vector<int> precompute_log(int n) {
    vector<int> log_table(n + 1);
    log_table[1] = 0;
    for (int i = 2; i <= n; ++i) {
        log_table[i] = log_table[i / 2] + 1; // 递推计算 log 值
    }
    return log_table;
}

// 查询区间 [l, r] 的或运算结果
int query_or(const vector<vector<int>>& st, const vector<int>& log_table, int l, int r) {
    int len = r - l + 1; // 区间长度
    int k = log_table[len]; // 对应的 log 值
    // 区间或运算：st[k][l] | st[k][r - (1 << k) + 1]
    return st[k][l] | st[k][r - (1 << k) + 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T; // 读取测试数据组数
    while (T--) {
        int n, k;
        cin >> n >> k; // 读取数组长度和最小值限制
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i]; // 读取数组元素
        }
        vector<int> double_a = a;
        double_a.insert(double_a.end(), a.begin(), a.end()); // 双倍数组，处理环状结构
        auto st = build_sparse_table(double_a); // 构建稀疏表
        vector<int> log_table = precompute_log(double_a.size()); // 预计算 log 表
        int max_ans = 0;
        for (int i = 0; i < n; ++i) {
            int left = 1, right = n;
            int ans_L = n;
            // 二分查找满足条件的最小长度
            while (left <= right) {
                int mid = (left + right) / 2;
                int r = i + mid - 1;
                int current_or = query_or(st, log_table, i, r); // 查询区间或值
                if (current_or >= k) {
                    ans_L = mid; // 满足条件，更新答案
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            max_ans = max(max_ans, ans_L - 1); // 更新最大操作次数
        }
        cout << max_ans << '\n'; // 输出结果
    }
    return 0;
}

代码实现（Python）

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    T = int(data[idx])  # 读取测试数据组数
    idx += 1
    for _ in range(T):
        n, k = int(data[idx]), int(data[idx + 1])  # 读取数组长度和最小值限制
        idx += 2
        a = list(map(int, data[idx:idx + n]))  # 读取数组元素
        idx += n
        double_a = a * 2  # 双倍数组，处理环状结构
        # 预计算 log 表
        max_len = len(double_a)
        log_table = [0] * (max_len + 1)
        for i in range(2, max_len + 1):
            log_table[i] = log_table[i // 2] + 1  # 递推计算 log 值
        max_level = log_table[max_len] + 1
        # 构建稀疏表
        st = [[0] * max_len for _ in range(max_level)]
        for i in range(max_len):
            st[0][i] = double_a[i]  # 第一层是原数组
        j = 1
        while (1 << j) <= max_len:
            for i in range(max_len - (1 << j) + 1):
                # 区间或运算：st[j][i] = st[j-1][i] | st[j-1][i + (1 << (j-1))]
                st[j][i] = st[j - 1][i] | st[j - 1][i + (1 << (j - 1))]
            j += 1
        max_ans = 0
        for i in range(n):
            left = 1
            right = n
            ans_L = n
            # 二分查找满足条件的最小长度
            while left <= right:
                mid = (left + right) // 2
                r = i + mid - 1
                if r >= len(double_a):
                    current_or = 0
                else:
                    length = mid
                    k_level = log_table[length]
                    if i + (1 << k_level) > r + 1:
                        part1 = st[k_level][i]
                        part2 = 0
                    else:
                        part1 = st[k_level][i]
                        part2 = st[k_level][r - (1 << k_level) + 1]
                    current_or = part1 | part2  # 查询区间或值
                if current_or >= k:
                    ans_L = mid  # 满足条件，更新答案
                    right = mid - 1
                else:
                    left = mid + 1
            max_ans = max(max_ans, ans_L - 1)  # 更新最大操作次数
        print(max_ans)  # 输出结果

if __name__ == "__main__":
    main()

代码实现（Java）

import java.util.*;
import java.io.*;

public class Main {
    // 构建稀疏表，用于快速查询区间或运算结果
    static int[][] buildSparseTable(int[] a) {
        int n = a.length;
        int maxLevel = 32 - Integer.numberOfLeadingZeros(n); // 计算最大层数
        int[][] st = new int[maxLevel][n]; // 初始化稀疏表
        for (int i = 0; i < n; i++) {
            st[0][i] = a[i]; // 第一层是原数组
        }
        for (int j = 1; j < maxLevel; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                // 区间或运算：st[j][i] = st[j-1][i] | st[j-1][i + (1 << (j-1))]
                st[j][i] = st[j - 1][i] | st[j - 1][i + (1 << (j - 1))];
            }
        }
        return st;
    }

    // 预计算 log 表，用于快速计算区间长度对应的 log 值
    static int[] precomputeLog(int n) {
        int[] logTable = new int[n + 1];
        logTable[1] = 0;
        for (int i = 2; i <= n; i++) {
            logTable[i] = logTable[i / 2] + 1; // 递推计算 log 值
        }
        return logTable;
    }

    // 查询区间 [l, r] 的或运算结果
    static int queryOr(int[][] st, int[] logTable, int l, int r) {
        int len = r - l + 1; // 区间长度
        int k = logTable[len]; // 对应的 log 值
        // 区间或运算：st[k][l] | st[k][r - (1 << k) + 1]
        return st[k][l] | st[k][r - (1 << k) + 1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 读取测试数据组数
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()); // 读取数组长度
            int k = Integer.parseInt(st.nextToken()); // 读取最小值限制
            int[] a = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken()); // 读取数组元素
            }
            int[] doubleA = new int[2 * n];
            System.arraycopy(a, 0, doubleA, 0, n); // 双倍数组，处理环状结构
            System.arraycopy(a, 0, doubleA, n, n);
            int[][] sparseTable = buildSparseTable(doubleA); // 构建稀疏表
            int[] logTable = precomputeLog(2 * n); // 预计算 log 表
            int maxAns = 0;
            for (int i = 0; i < n; i++) {
                int left = 1, right = n;
                int ansL = n;
                // 二分查找满足条件的最小长度
                while (left <= right) {
                    int mid = (left + right) / 2;
                    int rIdx = i + mid - 1;
                    if (rIdx >= 2 * n) { // 超出范围，跳过
                        right = mid - 1;
                        continue;
                    }
                    int currentOr = queryOr(sparseTable, logTable, i, rIdx); // 查询区间或值
                    if (currentOr >= k) {
                        ansL = mid; // 满足条件，更新答案
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                maxAns = Math.max(maxAns, ansL - 1); // 更新最大操作次数
            }
            System.out.println(maxAns); // 输出结果
        }
    }
}

题目内容

小苯有一个长为 $n$ 的数组 $a$，下标从 $0$ 到 $n-1$ ，他可以做如下操作:

• 对于每一个 $i(1 ≤ i ≤ n)$，令 ${b_i}={a_i}|a_{(i+1)％n}$，全部执行完后，再将 $a$ 数组赋值为 $b$数组，即再执行：$a_i =b_i(1≤i≤n)$。

小苯想知道，如果他想要 $a$ 的最小值不小于 $k$ 的话，最少需要执行多少次上述的操作，请你帮他算一算吧。(数据保证有解)。

输入描述

每个测试文件内都包含多组测试数据。

第一行一个正整数 $T(1 ≤ T≤ 1000)$，表示测试数据的组数

接下来对于每组测试数据，输入包含两行。

第一行两个整数 $n,k(1≤n≤2*10^5,0≤k≤2^{31})$表示数组 $a$ 的长度和最小值的限制。

第二行 $n$ 个整数 $a_i(0 ≤ a_i< 2^{31})$，表示数组 $a$。(保证所有测试数据中 $n$ 的总和不超过 $3*10^5$。

输出描述

输出包含 $T$ 行，对于每组测试数据，输出一行一个整数，表示最少要执行几次操作。

样例1

输入

1
5 4
1 7 4 2 7

输出

1

说明

只需操作 $1$ 次，数组 $a$ 变为：

{$7,7,6,7,7$}，满足最小值不小于 $4$ 。