scissor博客

logtrick

发表于 2026年6月16日数据结构
总字数 1442阅读时长 15 分钟浏览量 25

本文参考自灵神的相关题解：灵茶山艾府 - 力扣（LeetCode） 以及 LogTrick 方法解决子数组最值或计数问题 | 半方池水半方田

Logtrick 是在时间复杂度为 O(n2)O(n^2) 计算子数组的问题中，利用|、&、gcd、lcm等操作的性质进行优化的一种算法，通常用于求子数组经过一些操作（|、&、gcd、lcm）后的最值或计数问题。

或运算

按位或最大的最小子数组长度

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。

换言之，令 B_ij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(B_ik) ，其中 i <= k <= n - 1 。
一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

数据范围：
n == nums.length
1 <= n <= 10^5
0 <= nums[i] <= 10^9
暴力做法

有一个 O(n2)O(n^2) 暴力做法：从左到右正向遍历 nums，对于 x=nums[i]，从 i−1 开始倒着遍历 nums[j]，更新 nums[j]=nums[j] ∣ x，如果 nums[j] 变大，则更新 ans[j]=i−j+1。

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        for(int i = 0; i < n; i++){
            for(int j = i - 1; j >= 0; j--){
                int tmp =  nums[j];
                nums[j] |= nums[i];
                if(nums[j] > tmp){
                    ans[j] = i - j + 1;
                }
            }
        }
        return ans;
    }
}

该方法的主要思想是把子数组按位或的结果保存在 nums 中。

Logtrick
解法一

对于或运算来说，两个数字按位或的结果只会变大或者不变，而不会变小。因为对于某个二进制比特位，该位上的数字只会由 0 变成 1 ，而不会由 1 变成 0。

那么，我们来思考一个问题：对于起始位置为 ii 的子数组的按位或的结果，至多有多少种不同的结果？

根据或运算的性质，我们可以从 x=nums[i]x = nums[i] 开始，不断往右进行按位或，由于每次按位或的结果要么使 xx 不变，要么使 xx 的某些比特位由 0 变成 1。最坏情况下，从 x=0x = 0 出发，每次改变一个比特位，最多有 33 种不同的结果。

除了上面的结论，我们还可以得到另一个重要的结论：相同的按位或对应的子数组的右端点会形成一个连续的区间。（因为对于以 ii 为左端点的子数组，随着右端点的不断增大，按位或的结果是不可能减小的。）

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        // ors 维护以 i 为左端点的子数组的按位或的结果，按位或相同的为一组。
        // 对于 ors 内的每个数组 or，or[0] 为按位或的结果，or[1] 为对应子数组的右端点的最小值
        // 该列表从后向前遍历构建，列表中的元素按右端点从大到小排列（即第一个元素右端点最大，最后一个元素右端点最小）
        List<int[]> ors = new ArrayList<>();
        // 注意要倒着遍历，由于要求左端点固定的按位或的结果，这样在遍历到某个位置的时候
        // 右边数字的按位或的结果已经得到了
        for(int i = n - 1; i >= 0; i--){
            // 加入元素 0 ，从而在下面遍历的时候可以得到自身 nums[i] 的按位或的结果
            ors.add(new int[]{0, i});
            // 按位或的结果可能有重复指，k 用于原地去重
            // 可以参考：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/solutions/2807162/gen-zhao-wo-guo-yi-bian-shi-li-2ni-jiu-m-rvyk/
            int k = 0;
            for(int[] or : ors){
                or[0] |= nums[i];
                // 合并相同按位或值的状态，保留最小右端点
                if(ors.get(k)[0] == or[0]){
                    ors.get(k)[1] = or[1];
                }else{
                    ors.set(++k, or);
                }
            }
            // 移除合并后多余的元素（保留0到k的元素）
            ors.subList(k + 1, ors.size()).clear();
            // 合并后，ors.get(0)的按位或值即为从i到数组末尾的整个子数组的按位或结果（最大值）
            // ors.get(0)[1]是获得该值的最小右端点，子数组长度为 (右端点 - i + 1)
            ans[i] = ors.get(0)[1] - i + 1;
        }
        return ans;
    }
}

时间复杂度：O(nlongU)O(nlongU) ，其中 nn 为 numsnums 的长度，U=max(nums)U = max(nums) 。

解法二

我们可以把二进制数看成集合，二进制数第 ii 位为 1 表示 ii 在集合种。两个二进制数的或，就可以看成是两个集合的并集。

对于两个二进制数 aa 和 bb 。如果 a∣b=aa|b = a ，从集合的角度上看，bb 对应的集合是 aa 对应的集合的子集。

因此我们按照如下算法进行：

从左往右正向遍历 numsnums ，对于 x=nums[i]x = nums[i] ，从 i−1i- 1 开始倒着遍历 nums[j]nums[j] ：

  • 如果 nums[j]∣x≠nums[j]nums[j] | x \neq nums[j] ，说明 nums[j]nums[j] 可以变大（集合元素增多），更新 nums[j]=nums[j]∣xnums[j] = nums[j] | x ；
  • 如果 nums[j]∣x=nums[j]nums[j] | x = nums[j] ，从集合的角度来看，此时 xx 不仅是 nums[j]nums[j] 的子集，同时也是 nums[k](k<j)nums[k](k < j) 的子集（因为循环保证了每个集合都是其左侧相邻集合的子集），那么后续的循环都无法让元素变大，退出循环。
  • 在循环中，如果 nums[j]nums[j] 可以变大，则更新 ans[j]=i−j+1ans[j] = i - j + 1 。
class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        for(int i = 0; i < n; i++){
            for(int j = i - 1; j >= 0; j--){
                if((nums[j] | nums[i]) == nums[j]){
                    break;
                }
                nums[j] |= nums[i];
                ans[j] = i - j + 1;
            }
        }
        return ans;
    }
}

时间复杂度：O(nlongU)O(nlongU) ，其中 nn 为 numsnums 的长度，U=max(nums)U = max(nums) 。

898. 子数组按位或操作

给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。

子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。

子数组 是数组内连续的非空元素序列。

数据范围：
1 <= nums.length <= 5 * 10^4
0 <= nums[i] <= 10^9
解法一

与上一题的解法一类似，我们可以利用或运算的性质，与上一题不同的是，这题只需统计或运算的结果的个数，而不需要记录长度，因此我们可以直接用 Set 来存储或运算的结果。

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        int n = arr.length;
        Set<Integer> ans = new HashSet<>();
        Set<Integer> ors = new HashSet<>();
        // 此题并没有固定左右端点，因此可以从左往右，也可以从右往左遍历
        // 这里从左往右遍历，那么 ors 里存储的就是以 i 为右端点的子数组的或运算的结果
        for(int i = 0; i < n; i++){
            Set<Integer> tmp = new HashSet<>();
            tmp.add(arr[i]);
            for(int or : ors){
                tmp.add(or | arr[i]);
            }
            ans.addAll(tmp);
            ors = tmp;
        }
        return ans.size();
    }
}
解法二

从集合的角度思考。

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        int n = arr.length;
        Set<Integer> ans = new HashSet<>();
        for(int i = 0; i < n; i++){
            // 加入当前元素本身（单个元素的子数组）
            ans.add(arr[i]);
            for(int j = i - 1; j >= 0; j--){
                if((arr[j] | arr[i]) == arr[j]){
                    break;
                }
                // 更新子数组的按位或值：arr[j] 现在表示从 j 到 i 的子数组的或结果
                arr[j] |= arr[i];
                ans.add(arr[j]);
            }
        }
        return ans.size();
    }
}

与运算

1521. 找到最接近目标值的函数值

func(arr, l, r) {
    if (r < l) {
        return -1000000000
    }
    ans = arr[l]
    for (i = l + 1; i <= r; i++) {
        ans = ans & arr[i]
    }
    return ans
}

Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。
请你返回 |func(arr, l, r) - target| 的最小值。
请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。

数据范围：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

我们可以把二进制数看成集合，二进制数第 ii 位为 1 表示 ii 在集合种。两个二进制数的或，就可以看成是两个集合的交集。

对于两个二进制数 aa 和 bb 。如果 a&b=aa\&b = a ，从集合的角度上看，aa 对应的集合是 bb 对应的集合的子集。

class Solution {
    public int closestToTarget(int[] arr, int target) {
        int ans = 0x3f3f3f3f;
        int n = arr.length;
        for(int i = 0; i < n; i++){
            ans =  Math.min(ans, Math.abs(arr[i] - target));
            for(int j = i - 1; j >= 0 && (arr[i] & arr[j]) != arr[j]; j--){
                arr[j] &= arr[i];
                ans = Math.min(ans, Math.abs(arr[j] - target));
            }
        }
        return ans;
    }
}

3209. 子数组按位与值为 K 的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个子数组满足：子数组中所有元素按位 AND 的结果为 k 。

数据范围：
1 <= nums.length <= 10^5
0 <= nums[i], k <= 10^9
解法一

我们可以额外维护一个 List，存储子数组与运算的结果以及该结果对应的数量。

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long ans = 0;
        int n = nums.length;
        List<int[]> ands = new ArrayList<>();
        for(int i = 0; i < n; i++){
            int x = nums[i];
            ands.add(new int[]{x, 1});
            for(int[] and : ands){
                and[0] &= x;
                if(and[0] == k){
                    ans += and[1];
                }
            }
            int t = 0;
            for(int j = 1; j < ands.size(); j++){
                int[] and = ands.get(j);
                int[] last = ands.get(t);
                if(and[0] == last[0]){
                    last[1] += and[1];
                }else{
                    ands.set(++t, and);
                }
            }
            ands.subList(t + 1, ands.size()).clear();
        }
        return ans;
    }
}
解法二

二分查找。

由于每个元素都是其右侧元素的子集，所以从 nums[0]nums[0] 到 nums[i]nums[i] 的元素值是非递减的。既然是有序数组，我们可以在 [0,i][0,i] 中二分查找 kk 出现的次数。

class Solution {
    public long countSubarrays(int[] nums, int k) {
        long ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++){
            int x = nums[i];
            for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--){
                nums[j] &= x;
            }
            ans += find_right(nums, i + 1, k) - find_left(nums, i + 1, k);
        }
        return ans;
    }
    // 查找第一个大于等于k的位置
    public int find_left(int[] nums, int r, int k){
        int l = 0;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] >= k){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    // 查找第一个大于k的位置
    public int find_right(int[] nums, int r, int k){
        int l = 0;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] > k){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}

GCD

Problem - 475D - Codeforces

image

与上一题的解法一类似，使用原地去重的方法。由于本题需要统计最大公因数等于 viv_i 的子数组的个数，因此需要额外维护一个 mapmap 来统计每个最大公因数出现的次数。

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

typedef long long ll;
const int N = 100010;
ll a[N];
int n,q;
vector<vector<ll>> ands;
map<int,ll> cnt;

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    for(int i = 0; i < n; i++){
        ll x = a[i];
        cnt[x]++;
        ands.push_back({x, 1});
        for(int j = 0; j < ands.size() - 1; j++){
            vector<ll>& e = ands[j];
            ll newGcd = __gcd(e[0], x);
            cnt[newGcd] += e[1];
            e[0] = newGcd;
        }
        int k = 0;
        for(int j = 1; j < ands.size(); j++){
            if(ands[j][0] == ands[k][0]){
                ands[k][1] += ands[j][1];
            }else{
                ands[++k] = ands[j];
            }
        }
        ands.erase(ands.begin() + k + 1, ands.end());
    }
    scanf("%d", &q);
    while(q--){
        int v;
        scanf("%d", &v);
        printf("%lld\n", cnt[v]);
    }
    return 0;
}

3605. 数组的最小稳定性因子

给你一个整数数组 nums 和一个整数 maxC。

如果一个 子数组 的所有元素的最大公因数（简称 HCF） 大于或等于 2，则称该子数组是稳定的。

一个数组的 稳定性因子 定义为其 最长 稳定子数组的长度。

你 最多 可以修改数组中的 maxC 个元素为任意整数。

在最多 maxC 次修改后，返回数组的 最小 可能稳定性因子。如果没有稳定的子数组，则返回 0。

注意:

子数组 是数组中连续的元素序列。
数组的 最大公因数（HCF）是能同时整除数组中所有元素的最大整数。
如果长度为 1 的 子数组 中唯一元素大于等于 2，那么它是稳定的，因为 HCF([x]) = x。

数据范围：
1 <= n == nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= maxC <= n

看到最小化最大值，可以想到二分答案法。

原问题可以转换成一个判定问题：给定上界 upperupper ，需要通过至少 cntcnt 次修改，才能让 numsnums 的稳定性因子不超过 upperupper ，如果 cnt<maxCcnt < maxC ，说明答案 ⩽upper\leqslant upper ，否则说明答案 >upper> upper 。

遍历 numsnums ，计算以 ii 为右端点的所有子数组的最大公因数。对于最大公因数 ⩾2\geqslant 2 的以 ii 为右端点的最长子数组，如果其长度 >2> 2 ，那么必须修改元素的值。

此时贪心修改的元素一定是把当前 nums[1]nums[1] 修改成 11 。如果修改 ii 左边的元素，那么 nums[i]nums[i] 可能与后续元素组成不符合要求的子数组。而如果修改 nums[i]nums[i] ，那么包含 nums[i]nums[i] 的所有子数组的最大公因数均为 11，这样后续就不用考虑 nums[i]nums[i] 及其左边的所有元素了。

class Solution {
    public int minStable(int[] nums, int maxC) {
        int l = 0, r = nums.length;
        while(l < r){
            int mid = (l + r) >> 1;
            if(check(nums, mid) <= maxC){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    public int check(int[] nums, int len){
        List<int[]> gcds = new ArrayList<>();
        int cnt = 0;
        for(int i = 0; i < nums.length; i++){
            int x = nums[i];
            gcds.add(new int[]{x, i});
            for(int[] gcd : gcds){
                gcd[0] = Gcd(gcd[0], x);
            }
            int k = 0;
            for(int j = 1; j < gcds.size(); j++){
                if(gcds.get(j)[0] != gcds.get(k)[0]){
                    gcds.set(++k, gcds.get(j));
                }
            }
            gcds.subList(k + 1, gcds.size()).clear();
            if(gcds.get(0)[0] == 1){
                gcds.remove(0);
            }
            if(!gcds.isEmpty() && i - gcds.get(0)[1] + 1 > len){
                cnt++;
                gcds.clear();
            }
        }
        return cnt;
    }
    public int Gcd(int a, int b){
        if(b == 0){
            return a;
        }else{
            return Gcd(b, a % b);
        }
    }
}

Problem - 1632D - Codeforces

image

与上一题的思路类似，当遍历到 a[i]a[i] 不满足条件时，则修改 a[i]a[i] 为 11 ，这样才不会影响后面的数。

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

const int N = 200010;
int a[N];
int n;

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	vector<vector<int>> gcds;
	int cnt = 0;
	for(int i = 0; i < n; i++){
		int x = a[i];
		gcds.push_back({x, i});
		for(auto& gcd : gcds){
			gcd[0] = __gcd(x, gcd[0]);
		}
		int k = 0;
		for(int j = 1; j < gcds.size(); j++){
			if(gcds[j][0] != gcds[k][0]){
				gcds[++k] = gcds[j];
			}
		}
		gcds.erase(gcds.begin() + k + 1, gcds.end());
		bool find = false;
		for(int j = 0; j < gcds.size(); j++){
			if(j == gcds.size() - 1){
				int len = i - gcds[j][1] + 1;
				if(gcds[j][0] <= len){
					cnt++;
					find = true;
					break;
				}
			}else{
				int min_len = i - gcds[j + 1][1] + 2;
				int max_len = i - gcds[j][1] + 1;
				if(gcds[j][0] >= min_len && gcds[j][0] <= max_len){
					cnt++;
					find = true;
					break;
				}
			}
		}
		if(find){
			gcds.clear();
			gcds.push_back({2, i});
		}
		printf("%d ", cnt);
	}
	return 0;
}

logtrick

www.wystar.top/posts/logtrick/
作者
scissor567
发布时间
2026年6月16日
许可协议
CC BY-NC-SA 4.0