T3901.好子序列查询

https://leetcode.cn/problems/good-subsequence-queries/

【黄宇曦地球与空间科学学院】这集神了。

首先看到维护 $gcd$ 信息第一反应当然是 ST 表 / 线段树，然后发现带修，所以只能思考线段树怎么弄了。

我们把所有能被 $p$ 整除的扔进来，然后如果最后满足题目条件，那么必然有

\underset{p ∣ a_{i}}{gcd} (a_{i}) = p .

然后我们思考两种情况。

第一种情况是被 $p$ 整除的不是整个数组，那么直接就解决了。
第二种情况是被 $p$ 整除的是整个数组。那这个时候我们要考虑删一个数之后还能不能符合条件。
问题来了，如果对每一个第二种情况我们都扫一遍，那么时间复杂度将会是 $O (q n)$ ，这是非常不好的。所以我们思考优化。
一个朴素直觉是，这个数组如果不满足要求，那么长度不能太长。我们接下来加以论证。翻译一下条件，这说明我踢掉任何一个数，最后的 $gcd$ 都会变大。这说明每个数都有一个没有被公用的质因子 $p^{'}$ 。那么因为最后的 $gcd = p$ 并且踢掉之后 $gcd$ 会变大，这说明存在一个下标 $i$ （不妨令为 1）使得 $a_{1} = p \prod p^{'}$ 。而注意到 $p \prod p^{'} > p \cdot 2^{n - 1} \geq 2^{n}$ ，这意味着 $n \leq 30$ （更严谨地， $n \leq \log V$ ）。这个证明是不甚严谨的，但是通过完全类似的想法可以证明结论是正确的。
因此这意味着任何 $n > 30$ 都直接满足条件了。而对 $n \leq 30$ 的情况我们去直接枚举删掉每一个数之后会怎么样就可以了。
最后的时间复杂度是 $O (q \log n + n + q min {n, 30}) \sim O (q \log n + n)$ 。

cpp

class SegTree {
    int n;
    vector<int> s;
    int k;
    int lson(int x) { return x << 1; }
    int rson(int x) { return x << 1 | 1; }
    void push_up(int p) { s[p] = __gcd(s[lson(p)], s[rson(p)]); }
    void build(int l, int r, int p, const vector<int>& a) {
        if (l == r) {
            if (a[l] % k == 0)
                s[p] = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, lson(p), a);
        build(mid + 1, r, rson(p), a);
        push_up(p);
    }
    void modify(int pos, int val, int l, int r, int p) {
        if (l == r) {
            if (val % k == 0)
                s[p] = val;
            else
                s[p] = 0;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid)
            modify(pos, val, l, mid, lson(p));
        else
            modify(pos, val, mid + 1, r, rson(p));
        push_up(p);
    }

public:
    SegTree(int _n, const vector<int>& a, int k) : n(_n), s(_n << 2, 0), k(k) {
        build(0, _n - 1, 1, a);
    }
    void modify(int pos, int val) { modify(pos, val, 0, n - 1, 1); }
    int get() { return s[1]; }
};

class Solution {
public:
    int countGoodSubseq(vector<int>& nums, int p,
                        vector<vector<int>>& queries) {
        SegTree st(nums.size(), nums, p);
        int n = nums.size();
        int cnt = 0, ans = 0;
        for (int x : nums) {
            if (x % p == 0)
                cnt++;
        }
        for (auto q : queries) {
            int id = q[0], val = q[1];
            if (nums[id] % p != 0 && val % p == 0)
                cnt++;
            else if (nums[id] % p == 0 && val % p != 0)
                cnt--;
            nums[id] = val;
            st.modify(id, val);
            int cur = st.get();
            if (cur == p) {
                if (cnt < n)
                    ans++;
                else {
                    if (n > 30)
                        ans++;
                    else {
                        vector<int> pref(n + 1, 0), suf(n + 1, 0);
                        for (int i = 0; i < n; i++) {
                            pref[i + 1] = __gcd(pref[i], nums[i]);
                        }
                        for (int i = n - 1; i >= 0; i--) {
                            suf[i] = __gcd(suf[i + 1], nums[i]);
                        }
                        for (int i = 0; i < n; i++) {
                            if (__gcd(pref[i], suf[i + 1]) == p) {
                                ans++;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};

T3901.好子序列查询 ​

T3901.好子序列查询