Algorithm Programming Problem

3811.交替按位异或分割的数目 给你一个整数数组 nums 以及两个 互不相同 的整数 target1 和 target2。nums 的一个 分割 是指将其划分为一个或多个 连续且非空 的块，这些块在不重叠的情况下覆盖整个数组。 如果一个分割中各块元素的 按位异或 结果在 target1 和 target2 之间 交替 出现，且以 target1 开始，则称该分割是 有效的。 形式上，对于块 b1, b2, … ： XOR(b1) = target1 XOR(b2) = target2（如果存在） XOR(b3) = target1，以此类推。 返回 nums 的有效分割方案数，结果对 $10^9 $+ 7 取余。 注意： 如果单个块的 按位异或 结果等于 target1，则该分割也是有效的。 1 <= nums.length <= $10^5$ 0 <= nums[i], target1, target2 <= $10^5$ target1 != target2 思路 方法一：递归+记忆化搜索 点击展开/折叠代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { int mod = 1e9 + 7, t[2]; vector<vector<long long>> memo; long long dfs(int i, int state, vector<int> &nums) { if (i == nums.size()) { return 0; } if (memo[i][state] != -1) { return memo[i][state]; } long long res = 0; int cur = 0; for (int j = i; j < nums.size(); j++) { cur ^= nums[j]; if (cur == t[state]) { if (j == nums.size() - 1) { res = (res + 1) % mod; } else { res = (res + dfs(j + 1, state ^ 1, nums)) % mod; } } } return memo[i][state]=res; } public: int alternatingXOR(vector<int> &nums, int target1, int target2) { int n = nums.size(); t[0] = target1; t[1] = target2; memo.resize(n, vector<long long>(2, -1)); return dfs(0, 0, nums); } }; 时间复杂度：O(n)，其中n为数组nums的长度。 空间复杂度：O(n)，需要使用一个二维数组memo来存储中间结果。 不足以通过所有测试用例，超时。 ...

线段树是一种特殊的数据结构，它可以在 $O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 最简单的线段树的构建： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include <iostream> #include <vector> using namespace std; // 定义线段树的节点 struct Node { int l, r; // 左右子节点的下标 int sum; // 区间和 }; vector<Node> tree; // 存储线段树的数组 // 构建线段树 void build(int l, int r, int index, vector<int>& nums) { tree[index].l = l; tree[index].r = r; if (l == r) { // 叶子节点 tree[index].sum = nums[l]; return; } int mid = (l + r) / 2; build(l, mid, index * 2, nums); // 构建左子树 build(mid + 1, r, index * 2 + 1, nums); // 构建右子树 tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum; // 计算区间和 } // 区间查询 int query(int l, int r, int index) { if (tree[index].l >= l && tree[index].r <= r) { // 当前区间完全包含在查询区间内 return tree[index].sum; } int mid = (tree[index].l + tree[index].r) / 2; int sum = 0; if (l <= mid) { // 查询区间和左子树有交集 sum += query(l, r, index * 2); } if (r > mid) { // 查询区间和右子树有交集 sum += query(l, r, index * 2 + 1); } return sum; } // 单点修改 void update(int pos, int val, int index) { if (tree[index].l == tree[index].r) { // 叶子节点 tree[index].sum = val; return; } int mid = (tree[index].l + tree[index].r) / 2; if (pos <= mid) { // 修改的位置在左子树 update(pos, val, index * 2); } else { // 修改的位置在右子树 update(pos, val, index * 2 + 1); } tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum; // 更新区间和 } int main() { vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 原始数组 int n = nums.size(); // 数组长度 tree.resize(n * 4); // 线段树的大小为 4n build(0, n - 1, 1, nums); // 构建线段树 cout << query(0, 4, 1) << endl; // 查询区间 [0, 4] 的和 update(2, 10, 1); // 将第 2 个元素修改为 10 cout << query(0, 4, 1) << endl; // 查询区间 [0, 4] 的和 return 0; } 构建解释： 递归地将数组分为左右两个子数组，直到子数组长度为 1，此时该子数组的区间和就是该子数组的元素值。 ...