2025-01-04：不包含相邻元素的子序列的最大和用go语言，给定一

摘要：2025-01-04：不包含相邻元素的子序列的最大和。用go语言，给定一个整数数组 nums 和一个由二维数组 queries 组成的查询列表，其中每个查询的格式为 queries[i] = [posi, xi]。

2025-01-04：不包含相邻元素的子序列的最大和。用go语言，给定一个整数数组 nums 和一个由二维数组 queries 组成的查询列表，其中每个查询的格式为 queries[i] = [posi, xi]。

对于每个查询 i，首先将 nums[posi] 的值更新为 xi，然后计算在这一更新后，数组 nums 中所有不包含相邻元素的子序列的最大和。

最后，返回所有查询的结果之和。需要注意的是，由于最终答案可能非常大，因此要对其进行 1000000007 的取余处理。

请根据以上描述进行相关的处理。

-100000

queries[i] == [posi, xi]。

-100000

答案2025-01-04：

chatgpt[1]

题目来自leetcode3165。

1.定义了一个常量 MOD 为 1000000007，表示取余处理的数值。

2.实现了一个函数 maximumSumSubsequence，该函数接受一个整数数组 nums 以及一个查询列表 queries。首先创建一个长度为 nums 数组长度四倍的线段树 tree，然后初始化这颗线段树根据传入的 nums 数组。接着对 queries 中的每个查询进行处理：更新 nums 中指定位置的值，并计算不包含相邻元素的子序列的最大和，并将结果取余加到 ans 中。最终返回 ans。

3.定义了一个结构体 SegNode，包含四个成员变量 v00、v01、v10、v11，表示线段树中的四种情况。

4.实现了两个 SegNode 结构体的方法：Set 和 Best，分别用于设置节点的值和获取最佳值。

5.定义了一个结构体 SegTree，包含了一个整数 n 和一个指向 SegNode 结构体数组的指针 tree。

6.实现了一个 NewSegTree 函数用于创建一个 SegTree 结构体并初始化相关信息。

7.实现了 SegTree 结构体的方法：Init、Update、Query、internalInit、internalUpdate、pushup。这些方法用于初始化线段树、更新节点值、查询最佳值等功能。

8.在 main 函数中，给定了一个示例数组 nums 和查询 queries，然后调用 maximumSumSubsequence 函数计算不包含相邻元素的子序列的最大和，并打印结果。

总的时间复杂度：

• 初始化线段树的时间复杂度为 O(n)。• 每次查询的时间复杂度为 O(logn)。• 因此，总的时间复杂度为 O(n + q*logn)，其中 n 为数组长度，q 为查询次数。

总的额外空间复杂度：

• 线段树的空间复杂度为 O(n)。• 因此，总的额外空间复杂度为 O(n)，其中 n 为数组长度。package mainimport ("fmt""math")const MOD = 1000000007func maximumSumSubsequence(nums int, queries int) int {n := len(nums)tree := NewSegTree(n)tree.Init(nums)ans := int64(0)for _, q := range queries {tree.Update(q[0], q[1])ans = (ans + tree.Query) % MOD}return int(ans)}type SegNode struct {v00, v01, v10, v11 int64}func NewSegNode *SegNode {return &SegNode{0, 0, 0, 0}}func (sn *SegNode) Set(v int64) {sn.v00, sn.v01, sn.v10 = 0, 0, 0sn.v11 = int64(math.Max(float64(v), 0))}func (sn *SegNode) Best int64 {return sn.v11}type SegTree struct {n inttree *SegNode}func NewSegTree(n int) *SegTree {tree := make(*SegNode, n * 4 + 1)for i := range tree {tree[i] = NewSegNode}return &SegTree{n, tree}}func (st *SegTree) Init(nums int) {st.internalInit(nums, 1, 1, st.n)}func (st *SegTree) Update(x, v int) {st.internalUpdate(1, 1, st.n, x + 1, int64(v))}func (st *SegTree) Query int64 {return st.tree[1].Best}func (st *SegTree) internalInit(nums int, x, l, r int) {if l == r {st.tree[x].Set(int64(nums[l - 1]))return}mid := (l + r) / 2st.internalInit(nums, x * 2, l, mid)st.internalInit(nums, x * 2 + 1, mid + 1, r)st.pushup(x)}func (st *SegTree) internalUpdate(x, l, r int, pos int, v int64) {if l > pos || r

use std::cmp::max;const MOD: i64 = 1_000_000_007;#[derive(Clone)]struct SegNode {v00: i64,v01: i64,v10: i64,v11: i64,}impl SegNode {fn new -> Self {SegNode {v00: 0,v01: 0,v10: 0,v11: 0,}}fn set(&mut self, v: i64) {self.v00 = 0;self.v01 = 0;self.v10 = 0;self.v11 = max(v, 0);}fn best(&self) -> i64 {self.v11}}struct SegTree {n: usize,tree: Vec,}impl SegTree {fn new(n: usize) -> Self {let tree = vec![SegNode::new; n * 4];SegTree { n, tree }}fn init(&mut self, nums: &[i32]) {self.internal_init(nums, 1, 1, self.n);}fn update(&mut self, pos: usize, v: i32) {self.internal_update(1, 1, self.n, pos + 1, v as i64);}fn query(&self) -> i64 {self.tree[1].best}fn internal_init(&mut self, nums: &[i32], x: usize, l: usize, r: usize) {if l == r {self.tree[x].set(nums[l - 1] as i64);return;}let mid = (l + r) / 2;self.internal_init(nums, x * 2, l, mid);self.internal_init(nums, x * 2 + 1, mid + 1, r);self.push_up(x);}fn internal_update(&mut self, x: usize, l: usize, r: usize, pos: usize, v: i64) {if l > pos || r i64 {let n = nums.len;let mut tree = SegTree::new(n);tree.init(nums);let mut ans = 0;for (x, v) in queries {tree.update(*x, *v);ans = (ans + tree.query) % MOD;}ans}fn main {let nums = vec![3, 5, 9];let queries = vec![(1, -2), (0, -3)];let result = maximum_sum_subsequence(&nums, &queries);println!("{}", result);}

#include #include #include #define MOD 1000000007typedef struct {long long v00, v01, v10, v11;} SegNode;typedef struct {int n;SegNode* tree;} SegTree;SegNode newSegNode {SegNode node;node.v00 = 0;node.v01 = 0;node.v10 = 0;node.v11 = 0;return node;}void setSegNode(SegNode* sn, long long v) {sn->v00 = 0;sn->v01 = 0;sn->v10 = 0;sn->v11 = fmax(v, 0);}long long bestSegNode(SegNode* sn) {return sn->v11;}SegTree* newSegTree(int n) {SegTree* tree = (SegTree*)malloc(sizeof(SegTree));tree->n = n;tree->tree = (SegNode*)malloc(sizeof(SegNode) * (4 * n + 1));for (int i = 0; i tree[i] = newSegNode;}return tree;}void pushup(SegTree* st, int x);void internalInit(SegTree* st, int* nums, int x, int l, int r) {if (l == r) {setSegNode(&st->tree[x], (long long)nums[l - 1]);return;}int mid = (l + r) / 2;internalInit(st, nums, x * 2, l, mid);internalInit(st, nums, x * 2 + 1, mid + 1, r);pushup(st, x);}void pushup(SegTree* st, int x) {int l = x * 2;int r = x * 2 + 1;st->tree[x].v00 = fmax(st->tree[l].v00 + st->tree[r].v10, st->tree[l].v01 + st->tree[r].v00);st->tree[x].v01 = fmax(st->tree[l].v00 + st->tree[r].v11, st->tree[l].v01 + st->tree[r].v01);st->tree[x].v10 = fmax(st->tree[l].v10 + st->tree[r].v10, st->tree[l].v11 + st->tree[r].v00);st->tree[x].v11 = fmax(st->tree[l].v10 + st->tree[r].v11, st->tree[l].v11 + st->tree[r].v01);}void internalUpdate(SegTree* st, int x, int l, int r, int pos, long long v) {if (l > pos || r tree[x], v);return;}int mid = (l + r) / 2;internalUpdate(st, x * 2, l, mid, pos, v);internalUpdate(st, x * 2 + 1, mid + 1, r, pos, v);pushup(st, x);}long long query(SegTree* st) {return bestSegNode(&st->tree[1]);}void initSegTree(SegTree* st, int* nums) {internalInit(st, nums, 1, 1, st->n);}void updateSegTree(SegTree* st, int pos, int v) {internalUpdate(st, 1, 1, st->n, pos + 1, v);}long long maximumSumSubsequence(int* nums, int numsSize, int(*queries)[2], int queriesSize) {SegTree* tree = newSegTree(numsSize);initSegTree(tree, nums);long long ans = 0;for (int i = 0; i tree);free(tree);return ans;}int main {int nums = { 3, 5, 9 };int queries[2][2] = { {1, -2}, {0, -3} };long long result = maximumSumSubsequence(nums, 3, queries, 2);printf("%lld\n", result);return 0;}

#include #include #include #include const int MOD = 1000000007;class SegNode {public:long long v00, v01, v10, v11;SegNode : v00(0), v01(0), v10(0), v11(0) {}void set(long long v) {v00 = 0;v01 = 0;v10 = 0;v11 = std::max(v, 0LL);}long long best const {return v11;}};class SegTree {private:int n;std::vector tree;void pushup(int x) {int l = x * 2;int r = x * 2 + 1;tree[x].v00 = std::max(tree[l].v00 + tree[r].v10, tree[l].v01 + tree[r].v00);tree[x].v01 = std::max(tree[l].v00 + tree[r].v11, tree[l].v01 + tree[r].v01);tree[x].v10 = std::max(tree[l].v10 + tree[r].v10, tree[l].v11 + tree[r].v00);tree[x].v11 = std::max(tree[l].v10 + tree[r].v11, tree[l].v11 + tree[r].v01);}void internalInit(const std::vector& nums, int x, int l, int r) {if (l == r) {tree[x].set(static_cast(nums[l - 1]));return;}int mid = (l + r) / 2;internalInit(nums, x * 2, l, mid);internalInit(nums, x * 2 + 1, mid + 1, r);pushup(x);}void internalUpdate(int x, int l, int r, int pos, long long v) {if (l > pos || r & nums) {internalInit(nums, 1, 1, n);}void update(int pos, int v) {internalUpdate(1, 1, n, pos + 1, static_cast(v));}long long query const {return tree[1].best;}};long long maximumSumSubsequence(const std::vector& nums, const std::vector>& queries) {int n = nums.size;SegTree tree(n);tree.init(nums);long long ans = 0;for (const auto& query : queries) {tree.update(query.first, query.second);ans = (ans + tree.query) % MOD;}return ans;}int main {std::vector nums = { 3, 5, 9 };std::vector> queries = { {1, -2}, {0, -3} };long long result = maximumSumSubsequence(nums, queries);std::cout

# -*-coding:utf-8-*-class SegNode:def __init__(self):self.v00 = 0self.v01 = 0self.v10 = 0self.v11 = 0def set(self, v):self.v00 = 0self.v01 = 0self.v10 = 0self.v11 = max(v, 0)def best(self):return self.v11class SegTree:def __init__(self, n):self.n = nself.tree = [SegNode for _ in range(n * 4 + 1)]def init(self, nums):self._internal_init(nums, 1, 1, self.n)def update(self, x, v):self._internal_update(1, 1, self.n, x + 1, v)def query(self):return self.tree[1].bestdef _internal_init(self, nums, x, l, r):if l == r:self.tree[x].set(nums[l - 1])returnmid = (l + r) // 2self._internal_init(nums, x * 2, l, mid)self._internal_init(nums, x * 2 + 1, mid + 1, r)self._pushup(x)def _internal_update(self, x, l, r, pos, v):if l > pos or r