摘要
Title: 3097. 或值至少为 K 的最短子数组 II
Categories: 滑动窗口、子数组 OR/AND/GCD 通用模板

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

3097. 或值至少为 K 的最短子数组 II

题意

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。

思路

1. st + 二分 / 滑动窗口

比较好想的思路，通过二分或者滑动窗口，找到临界的为k的子数组，因为越长肯定或值越不小。所以固定一个端点，去单调数列中，找到临界的另一个端点即可

2. 子数组 OR/AND/GCD 通用模板

https://leetcode.cn/problems/shortest-subarray-with-or-at-least-k-ii/solutions/2716483/zi-shu-zu-orandgcd-tong-yong-mo-ban-pyth-n8xj/

用字典维护：key 是右端点为 i 的子数组 OR, value 是该子数组左端点的最大值

代码

# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    class SparseTable:
        def __init__(self, data: list, func=lambda x, y: x | y):
            """Initialize the Sparse Table with the given data and function."""
            self.func = func
            self.st = [list(data)]
            i, n = 1, len(self.st[0])
            while 2 * i <= n:
                pre = self.st[-1]
                self.st.append([func(pre[j], pre[j + i]) for j in range(n - 2 * i + 1)])
                i <<= 1

        def query(self, begin: int, end: int):
            """Query the combined result over the interval [begin, end]."""
            lg = (end - begin + 1).bit_length() - 1
            return self.func(self.st[lg][begin], self.st[lg][end - (1 << lg) + 1])

# ————————————————————— Division line ——————————————————————


class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        st = Std.SparseTable(nums, lambda x, y: x | y)
        n = len(nums)
        res = INF
        left = 0
        for right in range(n):
            while left <= right and st.query(left, right) >= k:
                res = Math.min(res, right - left + 1)
                left += 1
        return res if res != INF else -1

    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        st = Std.SparseTable(nums, lambda x, y: x | y)
        n = len(nums)
        res = INF
        for i in range(n):
            l = Std.bisect.bisect_left(range(i, n), k, lambda y: st.query(i, y))
            if l != n - i: res = Math.min(res, l + 1) # 如果 l = n - i，其实就是没找到，因为二分数组长度为 n - i + 1
        return res if res != INF else -1

    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf
        d = dict()  # key 是右端点为 i 的子数组 OR, value 是该子数组左端点的最大值
        for i, x in enumerate(nums):
            # 注意 key 是按照插入顺序排的，所以在相同 OR 时，会自动取到更大的 left 作为 value
            d = {or_ | x: left for or_, left in d.items()}
            d[x] = i  # 只包含 x 的子数组
            for or_, left in d.items():
                if or_ >= k:
                    ans = min(ans, i - left + 1)
        return ans if ans < inf else -1