Kimi LeetCode 3569. 分割数组后不同质数的最大数目 JavaScript实现-拓冰建站

以下是 LeetCode 3569「分割数组后不同质数的最大数目」的 JavaScript 实现。

核心思路

将数组在位置 `k`（`1 ≤ k < n`）处分割为左右两部分。对于某个质数 `p`：

- 若 `p` 在数组中只出现 1 次：无论怎么分割，它只能出现在一边，贡献 1。
- 若 `p` 出现 ≥ 2 次（首次在 `l`，末次在 `r`）：
- 当分割点 `k ∈ [l+1, r]` 时，`p` 会同时出现在左右两边，贡献 2（额外贡献 +1）。
- 否则贡献 1。

因此，每次查询的答案为：

> 不同质数的总数 + 最大额外贡献

其中「最大额外贡献」等价于：在区间 `[1, n-1]` 中，有多少个质数满足 `k ∈ [l+1, r]`。这需要用懒标记线段树维护区间加、区间最大值，以支持 `O(log n)` 的单点修改。

代码实现

```javascript
/**
* @param {number[]} nums
* @param {number[][]} queries
* @return {number[]}
*/
var maximumCount = function(nums, queries) {
const MX = 100000;
const n = nums.length;

// 筛法预处理质数
const isPrime = new Array(MX + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i <= MX; i++) {
if (isPrime[i]) {
for (let j = i * i; j <= MX; j += i) {
isPrime[j] = false;
}
}
}

// 懒标记线段树：区间加、区间最大值
class LazySegTree {
constructor(size, initVal) {
this.n = size;
this.mx = new Array(4 * size).fill(0);
this.lazy = new Array(4 * size).fill(0);
this._build(1, 0, size - 1, initVal);
}

_build(node, l, r, initVal) {
if (l === r) {
this.mx[node] = initVal;
return;
}
const mid = (l + r) >> 1;
this._build(node << 1, l, mid, initVal);
this._build(node << 1 | 1, mid + 1, r, initVal);
this.mx[node] = Math.max(this.mx[node << 1], this.mx[node << 1 | 1]);
}

_apply(node, val) {
this.mx[node] += val;
this.lazy[node] += val;
}

_push(node) {
const val = this.lazy[node];
if (val !== 0) {
this._apply(node << 1, val);
this._apply(node << 1 | 1, val);
this.lazy[node] = 0;
}
}

_update(node, l, r, ql, qr, val) {
if (ql <= l && r <= qr) {
this._apply(node, val);
return;
}
this._push(node);
const mid = (l + r) >> 1;
if (ql <= mid) this._update(node << 1, l, mid, ql, qr, val);
if (qr > mid) this._update(node << 1 | 1, mid + 1, r, ql, qr, val);
this.mx[node] = Math.max(this.mx[node << 1], this.mx[node << 1 | 1]);
}

update(l, r, val) {
if (l > r) return;
this._update(1, 0, this.n - 1, l, r, val);
}

query() {
return this.mx[1];
}
}

// pos[p] = 质数 p 的所有出现位置（有序数组）
const pos = new Map();
for (let i = 0; i < n; i++) {
const x = nums[i];
if (isPrime[x]) {
if (!pos.has(x)) pos.set(x, []);
pos.get(x).push(i);
}
}

// 初始化线段树：对出现 ≥ 2 次的质数，在 [l+1, r] 区间 +1
const seg = new LazySegTree(n, 0);
for (const arr of pos.values()) {
if (arr.length >= 2) {
const l = arr[0];
const r = arr[arr.length - 1];
const left = Math.max(l + 1, 1);
const right = Math.min(r, n - 1);
if (left <= right) seg.update(left, right, 1);
}
}

const ans = [];

// 从质数 p 的位置数组中删除索引 idx
function removeFromPrime(p, idx) {
const arr = pos.get(p);
const len = arr.length;

if (len === 1) {
pos.delete(p);
return;
}

const l = arr[0];
const r = arr[len - 1];

let posIdx = -1;
for (let i = 0; i < len; i++) {
if (arr[i] === idx) { posIdx = i; break; }
}
if (posIdx === -1) return;

arr.splice(posIdx, 1);

if (len === 2) {
// 从 2 个变 1 个，消除该质数的额外贡献
const left = Math.max(l + 1, 1);
const right = Math.min(r, n - 1);
if (left <= right) seg.update(left, right, -1);
} else {
const newL = arr[0];
const newR = arr[arr.length - 1];
if (idx === l) {
// 删除了最左端，范围从左边收缩
const left = Math.max(l + 1, 1);
const right = Math.min(newL, n - 1);
if (left <= right) seg.update(left, right, -1);
} else if (idx === r) {
// 删除了最右端，范围从右边收缩
const left = Math.max(newR + 1, 1);
const right = Math.min(r, n - 1);
if (left <= right) seg.update(left, right, -1);
}
// 若删除的是中间位置，[l, r] 不变，无需更新
}
}

// 向质数 p 的位置数组中添加索引 idx
function addToPrime(p, idx) {
if (!pos.has(p)) {
pos.set(p, [idx]);
return;
}

const arr = pos.get(p);
const len = arr.length;
const l = arr[0];
const r = arr[len - 1];

let insertPos = 0;
while (insertPos < len && arr[insertPos] < idx) insertPos++;
arr.splice(insertPos, 0, idx);

if (len === 1) {
// 从 1 个变 2 个，新增额外贡献
const newL = arr[0];
const newR = arr[1];
const left = Math.max(newL + 1, 1);
const right = Math.min(newR, n - 1);
if (left <= right) seg.update(left, right, 1);
} else {
const newL = arr[0];
const newR = arr[arr.length - 1];
if (idx < l) {
// 向左扩展
const left = Math.max(idx + 1, 1);
const right = Math.min(l, n - 1);
if (left <= right) seg.update(left, right, 1);
} else if (idx > r) {
// 向右扩展
const left = Math.max(r + 1, 1);
const right = Math.min(idx, n - 1);
if (left <= right) seg.update(left, right, 1);
}
// 若插入到中间，[l, r] 不变，无需更新
}
}