题目截图

题目分析

不能取相邻的，就是打家劫舍
然后更改某一个值就是单点更新
更新后，需要更新区间的值
需要注意的是，使用分治时需要考虑到一头一尾的问题，所以有4种情况（选or不选在两个位置）
这四种情况需要在maintain中维护

ac code

// f00 表示第一个数一定不选，最后一个数一定不选
// f01 表示第一个数一定不选，最后一个数可选可不选
// f10 表示第一个数可选可不选，最后一个数一定不选
// f11 表示第一个数可选可不选，最后一个数可选可不选，也就是没有任何限制
// 答案是根节点的f11，没有任何限制
// 按照分治的思想结合线段树处理
// 线段树包含以上四个f进行maintain
type data struct {f00, f01, f10, f11 int}
type seg []data 

func(t seg) maintain(o int) {
    // 左右孩子
    a, b := t[o<<1], t[o<<1|1]
    t[o] = data {
        max(a.f00 + b.f10, a.f01 + b.f00),
        max(a.f00 + b.f11, a.f01 + b.f01),
        max(a.f10 + b.f10, a.f11 + b.f00),
        max(a.f10 + b.f11, a.f11 + b.f01),
    }
}

func(t seg) build (a []int, o, l, r int) {
    if l == r {
        // 边界只需考虑f11，其他都不能取
        t[o].f11 = max(a[l], 0)
        return
    }
    m := (l + r) >> 1
    t.build(a, o<<1, l, m)
    t.build(a, o<<1|1, m + 1, r)
    t.maintain(o)
}

// 单点更新
func(t seg) update(o, l, r, i, val int) {
    if l == r {
        // 边界只需考虑f11，其他都不能取
        t[o].f11 = max(val, 0)
        return
    }
    m := (l + r) >> 1
    if i <= m {
        t.update(o<<1, l, m, i, val)
    } else {
        t.update(o<<1|1, m + 1, r, i, val)
    }
    t.maintain(o)
}

func maximumSumSubsequence(nums []int, queries [][]int) (ans int) {
    n := len(nums)
    t := make(seg, 2<<bits.Len(uint(n)))
    t.build(nums, 1, 0, n - 1)
    for _, q := range queries {
        t.update(1, 0, n - 1, q[0], q[1])
        ans += t[1].f11 // f11是整个数组的没有限制
    }
    return ans % 1_000_000_007
}