3901. 好子序列查询

Hard

题目描述

给你一个长度为 n 的整数数组 nums 和一个整数 p。

nums 的一个非空子序列被称为好的，如果：

它的长度严格小于 n。
它的所有元素的最大公约数（GCD）恰好等于 p。

同时给你一个长度为 q 的二维整数数组 queries，其中每个 queries[i] = [indi, vali] 表示你应该将 nums[indi] 更新为 vali。

在每次查询后，判断当前数组中是否存在任何好子序列。

返回存在好子序列的查询次数。

术语 gcd(a, b) 表示 a 和 b 的最大公约数。

示例 1：

输入：nums = [4,8,12,16], p = 2, queries = [[0,3],[2,6]]
输出：1

示例 2：

输入：nums = [4,5,7,8], p = 3, queries = [[0,6],[1,9],[2,3]]
输出：2

示例 3：

输入：nums = [5,7,9], p = 2, queries = [[1,4],[2,8]]
输出：0

提示：

2 <= n == nums.length <= 5 * 10^4
1 <= nums[i] <= 5 * 10^4
1 <= queries.length <= 5 * 10^4
queries[i] = [indi, vali]
1 <= vali, p <= 5 * 10^4
0 <= indi <= n - 1

解题思路

只可能选择能被 p 整除的元素。把这些元素除以 p 后，问题变为：能否选出一个长度小于 n、GCD 为 1 的非空子序列。

关键观察：

一组数存在 GCD 为 1 的子集，当且仅当这组数整体的 GCD 为 1。
如果能被 p 整除的元素少于 n 个，那么取全部有效元素已经是长度小于 n 的子序列，只需检查它们的 GCD 是否为 1。
如果全部 n 个元素都有效，则必须至少删除一个元素。只要存在任意真子集的 GCD 为 1，就一定存在一个长度为 n - 1 的子集 GCD 为 1。
删除下标 i 后的 GCD 大于 1，当且仅当存在某个质因子恰好出现在另外 n - 1 个元素中。把这种质因子唯一缺失的下标记为“不可删除”。只要并非所有下标都不可删除，就存在合法子序列。

动态维护：

用 GCD 线段树维护所有有效缩放值；无效元素记为 0，因为 gcd(0, x) = x。
对每个质因子维护出现次数和出现下标的异或值。当次数为 n - 1 时，通过“所有下标异或值”异或“出现下标异或值”得到唯一缺失下标。
每次更新只删除旧值、加入新值所含的不同质因子，并在线段树中做一次单点更新。
查询时先要求线段树根节点为 1；若有效元素不足 n 个则答案为真，否则还要求至少存在一个可删除下标。

代码实现

class Solution {
public:
    int countGoodSubseq(vector<int>& nums, int p, vector<vector<int>>& queries) {
        int n = nums.size();
        const int MAX_VALUE = 50000;

        vector<int> spf(MAX_VALUE + 1);
        iota(spf.begin(), spf.end(), 0);
        for (int i = 2; i * i <= MAX_VALUE; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= MAX_VALUE; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }

        auto getFactors = [&](int x) {
            vector<int> factors;
            while (x > 1) {
                int prime = spf[x];
                factors.push_back(prime);
                while (x % prime == 0) x /= prime;
            }
            return factors;
        };

        int size = 1;
        while (size < n) size <<= 1;
        vector<int> tree(size * 2);
        vector<int> reduced(n);
        vector<int> primeCount(MAX_VALUE + 1);
        vector<int> primeXor(MAX_VALUE + 1);
        int activeCount = 0;

        for (int index = 0; index < n; index++) {
            int value = nums[index] % p == 0 ? nums[index] / p : 0;
            reduced[index] = value;
            tree[size + index] = value;
            if (value == 0) continue;

            activeCount++;
            for (int prime : getFactors(value)) {
                primeCount[prime]++;
                primeXor[prime] ^= index;
            }
        }
        for (int node = size - 1; node > 0; node--) {
            tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
        }

        int allIndicesXor = 0;
        for (int index = 0; index < n; index++) allIndicesXor ^= index;

        vector<int> witnessFrequency(n);
        int coveredIndices = 0;

        auto addWitness = [&](int prime) {
            if (primeCount[prime] != n - 1) return;
            int missingIndex = allIndicesXor ^ primeXor[prime];
            if (witnessFrequency[missingIndex]++ == 0) coveredIndices++;
        };
        auto removeWitness = [&](int prime) {
            if (primeCount[prime] != n - 1) return;
            int missingIndex = allIndicesXor ^ primeXor[prime];
            if (--witnessFrequency[missingIndex] == 0) coveredIndices--;
        };

        for (int prime = 2; prime <= MAX_VALUE; prime++) {
            addWitness(prime);
        }

        auto removeValue = [&](int index, int value) {
            if (value == 0) return;
            activeCount--;
            for (int prime : getFactors(value)) {
                removeWitness(prime);
                primeCount[prime]--;
                primeXor[prime] ^= index;
                addWitness(prime);
            }
        };
        auto addValue = [&](int index, int value) {
            if (value == 0) return;
            activeCount++;
            for (int prime : getFactors(value)) {
                removeWitness(prime);
                primeCount[prime]++;
                primeXor[prime] ^= index;
                addWitness(prime);
            }
        };
        auto updateTree = [&](int index, int value) {
            int node = size + index;
            tree[node] = value;
            for (node >>= 1; node > 0; node >>= 1) {
                tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
            }
        };

        int result = 0;
        for (const auto& query : queries) {
            int index = query[0];
            int value = query[1] % p == 0 ? query[1] / p : 0;

            removeValue(index, reduced[index]);
            reduced[index] = value;
            addValue(index, value);
            updateTree(index, value);

            if (tree[1] == 1 && (activeCount < n || coveredIndices < n)) {
                result++;
            }
        }

        return result;
    }
};

from math import gcd


class Solution:
    def countGoodSubseq(self, nums: list[int], p: int, queries: list[list[int]]) -> int:
        n = len(nums)
        max_value = 50000

        spf = list(range(max_value + 1))
        for i in range(2, int(max_value**0.5) + 1):
            if spf[i] == i:
                for j in range(i * i, max_value + 1, i):
                    if spf[j] == j:
                        spf[j] = i

        def get_factors(value):
            factors = []
            while value > 1:
                prime = spf[value]
                factors.append(prime)
                while value % prime == 0:
                    value //= prime
            return factors

        size = 1
        while size < n:
            size *= 2
        tree = [0] * (size * 2)
        reduced = [0] * n
        prime_count = [0] * (max_value + 1)
        prime_xor = [0] * (max_value + 1)
        active_count = 0

        for index, original in enumerate(nums):
            value = original // p if original % p == 0 else 0
            reduced[index] = value
            tree[size + index] = value
            if value == 0:
                continue
            active_count += 1
            for prime in get_factors(value):
                prime_count[prime] += 1
                prime_xor[prime] ^= index

        for node in range(size - 1, 0, -1):
            tree[node] = gcd(tree[node * 2], tree[node * 2 + 1])

        all_indices_xor = 0
        for index in range(n):
            all_indices_xor ^= index

        witness_frequency = [0] * n
        covered_indices = 0

        def add_witness(prime):
            nonlocal covered_indices
            if prime_count[prime] != n - 1:
                return
            missing_index = all_indices_xor ^ prime_xor[prime]
            if witness_frequency[missing_index] == 0:
                covered_indices += 1
            witness_frequency[missing_index] += 1

        def remove_witness(prime):
            nonlocal covered_indices
            if prime_count[prime] != n - 1:
                return
            missing_index = all_indices_xor ^ prime_xor[prime]
            witness_frequency[missing_index] -= 1
            if witness_frequency[missing_index] == 0:
                covered_indices -= 1

        for prime in range(2, max_value + 1):
            add_witness(prime)

        def remove_value(index, value):
            nonlocal active_count
            if value == 0:
                return
            active_count -= 1
            for prime in get_factors(value):
                remove_witness(prime)
                prime_count[prime] -= 1
                prime_xor[prime] ^= index
                add_witness(prime)

        def add_value(index, value):
            nonlocal active_count
            if value == 0:
                return
            active_count += 1
            for prime in get_factors(value):
                remove_witness(prime)
                prime_count[prime] += 1
                prime_xor[prime] ^= index
                add_witness(prime)

        def update_tree(index, value):
            node = size + index
            tree[node] = value
            node //= 2
            while node:
                tree[node] = gcd(tree[node * 2], tree[node * 2 + 1])
                node //= 2

        result = 0
        for index, original in queries:
            value = original // p if original % p == 0 else 0
            remove_value(index, reduced[index])
            reduced[index] = value
            add_value(index, value)
            update_tree(index, value)

            if tree[1] == 1 and (active_count < n or covered_indices < n):
                result += 1

        return result

public class Solution {
    public int CountGoodSubseq(int[] nums, int p, int[][] queries) {
        int n = nums.Length;
        const int MaxValue = 50000;

        int[] spf = new int[MaxValue + 1];
        for (int i = 0; i <= MaxValue; i++) spf[i] = i;
        for (int i = 2; i * i <= MaxValue; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= MaxValue; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }

        List<int> GetFactors(int value) {
            var factors = new List<int>();
            while (value > 1) {
                int prime = spf[value];
                factors.Add(prime);
                while (value % prime == 0) value /= prime;
            }
            return factors;
        }

        int Gcd(int a, int b) {
            while (b != 0) {
                int next = a % b;
                a = b;
                b = next;
            }
            return a;
        }

        int size = 1;
        while (size < n) size <<= 1;
        int[] tree = new int[size * 2];
        int[] reduced = new int[n];
        int[] primeCount = new int[MaxValue + 1];
        int[] primeXor = new int[MaxValue + 1];
        int activeCount = 0;

        for (int index = 0; index < n; index++) {
            int value = nums[index] % p == 0 ? nums[index] / p : 0;
            reduced[index] = value;
            tree[size + index] = value;
            if (value == 0) continue;

            activeCount++;
            foreach (int prime in GetFactors(value)) {
                primeCount[prime]++;
                primeXor[prime] ^= index;
            }
        }
        for (int node = size - 1; node > 0; node--) {
            tree[node] = Gcd(tree[node * 2], tree[node * 2 + 1]);
        }

        int allIndicesXor = 0;
        for (int index = 0; index < n; index++) allIndicesXor ^= index;

        int[] witnessFrequency = new int[n];
        int coveredIndices = 0;

        void AddWitness(int prime) {
            if (primeCount[prime] != n - 1) return;
            int missingIndex = allIndicesXor ^ primeXor[prime];
            if (witnessFrequency[missingIndex]++ == 0) coveredIndices++;
        }

        void RemoveWitness(int prime) {
            if (primeCount[prime] != n - 1) return;
            int missingIndex = allIndicesXor ^ primeXor[prime];
            if (--witnessFrequency[missingIndex] == 0) coveredIndices--;
        }

        for (int prime = 2; prime <= MaxValue; prime++) AddWitness(prime);

        void RemoveValue(int index, int value) {
            if (value == 0) return;
            activeCount--;
            foreach (int prime in GetFactors(value)) {
                RemoveWitness(prime);
                primeCount[prime]--;
                primeXor[prime] ^= index;
                AddWitness(prime);
            }
        }

        void AddValue(int index, int value) {
            if (value == 0) return;
            activeCount++;
            foreach (int prime in GetFactors(value)) {
                RemoveWitness(prime);
                primeCount[prime]++;
                primeXor[prime] ^= index;
                AddWitness(prime);
            }
        }

        void UpdateTree(int index, int value) {
            int node = size + index;
            tree[node] = value;
            for (node >>= 1; node > 0; node >>= 1) {
                tree[node] = Gcd(tree[node * 2], tree[node * 2 + 1]);
            }
        }

        int result = 0;
        foreach (int[] query in queries) {
            int index = query[0];
            int value = query[1] % p == 0 ? query[1] / p : 0;

            RemoveValue(index, reduced[index]);
            reduced[index] = value;
            AddValue(index, value);
            UpdateTree(index, value);

            if (tree[1] == 1 && (activeCount < n || coveredIndices < n)) {
                result++;
            }
        }

        return result;
    }
}

var countGoodSubseq = function(nums, p, queries) {
    const n = nums.length;
    const maxValue = 50000;

    const spf = new Int32Array(maxValue + 1);
    for (let i = 0; i <= maxValue; i++) spf[i] = i;
    for (let i = 2; i * i <= maxValue; i++) {
        if (spf[i] !== i) continue;
        for (let j = i * i; j <= maxValue; j += i) {
            if (spf[j] === j) spf[j] = i;
        }
    }

    const getFactors = value => {
        const factors = [];
        while (value > 1) {
            const prime = spf[value];
            factors.push(prime);
            while (value % prime === 0) value /= prime;
        }
        return factors;
    };

    const gcd = (a, b) => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };

    let size = 1;
    while (size < n) size *= 2;
    const tree = new Int32Array(size * 2);
    const reduced = new Int32Array(n);
    const primeCount = new Int32Array(maxValue + 1);
    const primeXor = new Int32Array(maxValue + 1);
    let activeCount = 0;

    for (let index = 0; index < n; index++) {
        const value = nums[index] % p === 0 ? nums[index] / p : 0;
        reduced[index] = value;
        tree[size + index] = value;
        if (value === 0) continue;

        activeCount++;
        for (const prime of getFactors(value)) {
            primeCount[prime]++;
            primeXor[prime] ^= index;
        }
    }
    for (let node = size - 1; node > 0; node--) {
        tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
    }

    let allIndicesXor = 0;
    for (let index = 0; index < n; index++) allIndicesXor ^= index;

    const witnessFrequency = new Int32Array(n);
    let coveredIndices = 0;

    const addWitness = prime => {
        if (primeCount[prime] !== n - 1) return;
        const missingIndex = allIndicesXor ^ primeXor[prime];
        if (witnessFrequency[missingIndex]++ === 0) coveredIndices++;
    };

    const removeWitness = prime => {
        if (primeCount[prime] !== n - 1) return;
        const missingIndex = allIndicesXor ^ primeXor[prime];
        if (--witnessFrequency[missingIndex] === 0) coveredIndices--;
    };

    for (let prime = 2; prime <= maxValue; prime++) addWitness(prime);

    const removeValue = (index, value) => {
        if (value === 0) return;
        activeCount--;
        for (const prime of getFactors(value)) {
            removeWitness(prime);
            primeCount[prime]--;
            primeXor[prime] ^= index;
            addWitness(prime);
        }
    };

    const addValue = (index, value) => {
        if (value === 0) return;
        activeCount++;
        for (const prime of getFactors(value)) {
            removeWitness(prime);
            primeCount[prime]++;
            primeXor[prime] ^= index;
            addWitness(prime);
        }
    };

    const updateTree = (index, value) => {
        let node = size + index;
        tree[node] = value;
        for (node = Math.floor(node / 2); node > 0; node = Math.floor(node / 2)) {
            tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
        }
    };

    let result = 0;
    for (const [index, original] of queries) {
        const value = original % p === 0 ? original / p : 0;
        removeValue(index, reduced[index]);
        reduced[index] = value;
        addValue(index, value);
        updateTree(index, value);

        if (tree[1] === 1 && (activeCount < n || coveredIndices < n)) {
            result++;
        }
    }

    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	分析
时间复杂度	O(V log log V + (N + Q)(log V + log N))
空间复杂度	O(V + N)

其中 V = 50000。最小质因子筛为 O(V log log V)；每个值只枚举其不同质因子，单次更新再做一次 O(log N) 的线段树更新。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析