以下是 LeetCode 3901「好子序列查询」的 Java 实现基于线段树维护 GCD。核心思路1. 关键观察只有 p 的倍数才可能出现在 GCD 为 p 的子序列中。非 p 倍数的元素可以直接忽略。2. 线段树维护将所有非 p 倍数的位置视为 0线段树维护所有 p 倍数的 GCD。3. 判断条件- 若整体 GCD ≠ p则不存在好子序列- 若存在非 p 倍数的元素cnt n则所有 p 倍数构成的子序列长度 n直接成立- 若所有元素都是 p 倍数cnt n且 n 6则一定存在一个元素删除后 GCD 仍为 p- 若 n ≤ 6 且所有元素都是 p 倍数需要暴力枚举删除哪个元素时间复杂度O((n q) \log n)空间复杂度O(n)Java 代码javaclass SegNode {int l, r;int g;SegNode(int l, int r) {this.l l;this.r r;this.g 0;}}class SegmentTree {SegNode[] tr;SegmentTree(int n) {tr new SegNode[n 2];build(1, 1, n);}void build(int u, int l, int r) {tr[u] new SegNode(l, r);if (l r) {return;}int mid (l r) 1;build(u 1, l, mid);build(u 1 | 1, mid 1, r);}void pushup(int u) {tr[u].g gcd(tr[u 1].g, tr[u 1 | 1].g);}void modify(int u, int x, int v) {if (tr[u].l tr[u].r) {tr[u].g v;return;}int mid (tr[u].l tr[u].r) 1;if (x mid) {modify(u 1, x, v);} else {modify(u 1 | 1, x, v);}pushup(u);}int query(int u, int l, int r) {if (l r) {return 0;}if (tr[u].l l tr[u].r r) {return tr[u].g;}int mid (tr[u].l tr[u].r) 1;if (r mid) {return query(u 1, l, r);}if (l mid) {return query(u 1 | 1, l, r);}return gcd(query(u 1, l, mid), query(u 1 | 1, mid 1, r));}private int gcd(int a, int b) {while (b ! 0) {int t a % b;a b;b t;}return a;}}class Solution {private int gcd(int a, int b) {while (b ! 0) {int t a % b;a b;b t;}return a;}public int countGoodSubseq(int[] nums, int p, int[][] queries) {int n nums.length;SegmentTree tree new SegmentTree(n);int cnt 0;// 初始化将 p 的倍数加入线段树for (int i 0; i n; i) {if (nums[i] % p 0) {tree.modify(1, i 1, nums[i]);cnt;}}int ans 0;for (int[] q : queries) {int idx q[0], val q[1];// 移除旧值if (nums[idx] % p 0) {tree.modify(1, idx 1, 0);--cnt;}// 加入新值if (val % p 0) {tree.modify(1, idx 1, val);cnt;}nums[idx] val;// 情况1整体GCD不等于p不可能存在好子序列if (tree.tr[1].g ! p) {continue;}// 情况2存在非p倍数元素所有p倍数构成的子序列长度n直接成立// 情况3n6时所有元素都是p倍数一定能删一个保持GCDpif (cnt n || n 6) {ans;continue;}// 情况4n6且所有元素都是p倍数暴力枚举删除哪个元素boolean ok false;for (int i 1; i n; i) {int leftG tree.query(1, 1, i - 1);int rightG tree.query(1, i 1, n);if (gcd(leftG, rightG) p) {ok true;break;}}if (ok) {ans;}}return ans;}}关键点说明- 线段树下标使用 1-based 索引i 1方便子节点计算 u 1 和 u 1 | 1- n 6 的优化当所有元素都是 p 的倍数且整体 GCD 为 p 时若数组长度大于 6则必然存在一个元素删除后 GCD 仍为 p。这是因为每个数最多贡献一个关键质因子而大于 6 个数时质因子覆盖必然有冗余。- 空区间查询返回 0gcd(0, x) x所以空区间返回 0 不影响结果