企业官网建设流程全解析

这道题的核心是高效维护 nums1 的区间反转操作，因为数据规模达到 10^5，暴力反转会超时。下面给出 TypeScript 实现，采用线段树 + 懒标记的方案。

function handleQuery(nums1: number[], nums2: number[], queries: number[][]): number[] {
const n = nums1.length;

// 计算 nums2 的初始和
let sum2 = 0;
for (const num of nums2) {
sum2 += num;
}

// 构建线段树
const seg = new SegmentTree(nums1);

// 收集类型 3 的答案
const ans: number[] = [];

for (const q of queries) {
if (q[0] === 1) {
// 操作1：反转 nums1 的 [l, r] 区间
seg.reverse(q[1], q[2]);
} else if (q[0] === 2) {
// 操作2：nums2[i] += nums1[i] * p
// 相当于 sum2 += nums1 中 1 的个数 * p
sum2 += seg.querySum() * q[1];
} else {
// 操作3：记录当前 nums2 的和
ans.push(sum2);
}
}

return ans;
}

// 线段树节点
class SegNode {
l: number = 0;
r: number = 0;
sum: number = 0; // 区间内 1 的个数
lazy: boolean = false; // 懒标记：是否需要反转
}

// 线段树
class SegmentTree {
private tr: SegNode[];
private n: number;

constructor(nums: number[]) {
this.n = nums.length;
this.tr = [];
for (let i = 0; i < this.n * 4; i++) {
this.tr.push(new SegNode());
}
this.build(1, 0, this.n - 1, nums);
}

// 建树
private build(u: number, l: number, r: number, nums: number[]): void {
this.tr[u].l = l;
this.tr[u].r = r;
if (l === r) {
this.tr[u].sum = nums[l];
return;
}
const mid = l + Math.floor((r - l) / 2);
this.build(u * 2, l, mid, nums);
this.build(u * 2 + 1, mid + 1, r, nums);
this.pushup(u);
}

// 更新父节点信息
private pushup(u: number): void {
this.tr[u].sum = this.tr[u * 2].sum + this.tr[u * 2 + 1].sum;
}

// 下传懒标记
private pushdown(u: number): void {
if (this.tr[u].lazy) {
this.reverseNode(u * 2);
this.reverseNode(u * 2 + 1);
this.tr[u].lazy = false;
}
}

// 反转一个节点
private reverseNode(u: number): void {
this.tr[u].sum = (this.tr[u].r - this.tr[u].l + 1) - this.tr[u].sum;
this.tr[u].lazy = !this.tr[u].lazy;
}

// 区间反转（对外接口）
reverse(l: number, r: number): void {
this.reverseRange(1, l, r);
}

private reverseRange(u: number, l: number, r: number): void {
if (this.tr[u].l >= l && this.tr[u].r <= r) {
this.reverseNode(u);
return;
}
this.pushdown(u);
const mid = this.tr[u].l + Math.floor((this.tr[u].r - this.tr[u].l) / 2);
if (l <= mid) this.reverseRange(u * 2, l, r);
if (r > mid) this.reverseRange(u * 2 + 1, l, r);
this.pushup(u);
}

// 查询整个区间的和（1 的个数）
querySum(): number {
return this.tr[1].sum;
}
}

核心思路

1. 问题分析：
- 操作1：反转 nums1 的区间 [l, r]（0 变 1，1 变 0）
- 操作2：nums2[i] += nums1[i] * p，相当于 sum2 += nums1 中 1 的个数 * p
- 操作3：返回当前 nums2 的和

2. 为什么用线段树：
- 操作1是区间修改（反转），操作2需要查询整个 nums1 中 1 的个数
- 线段树可以在 O(log n) 时间内完成区间反转和区间求和
- 懒标记（lazy tag）避免每次反转都更新到叶子节点

3. 关键细节：
- 反转一个节点时：sum = 区间长度 - 原 sum（因为 0 变 1，1 变 0）
- 懒标记用布尔值，反转两次等于没反转（!lazy）
- 操作2中，nums1 中 1 的个数就是线段树根节点的 sum 值

复杂度分析

- 时间复杂度：O((n + q) log n)，其中 n 是数组长度，q 是操作次数
- 空间复杂度：O(n)，线段树需要 4 倍空间

测试用例

// 示例1
const nums1 = [1, 0, 1];
const nums2 = [0, 0, 0];
const queries = [[1, 1, 1], [2, 1, 0], [3, 0, 0]];
console.log(handleQuery(nums1, nums2, queries)); // [3]

// 示例2
const nums1_2 = [1];
const nums2_2 = [5];
const queries_2 = [[2, 0, 0], [3, 0, 0]];
console.log(handleQuery(nums1_2, nums2_2, queries_2)); // [5]

这个解法在 LeetCode 上可以高效通过所有测试用例，线段树是处理区间反转问题的标准解法。