LC 100306. 不包含相邻元素的子序列的最大和

https://leetcode.cn/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/description/

这题还是线段树，但是一个节点(区间)上需要考虑4个情况，是否选择left/right:

left = 0, right = 0
left = 1, right = 0
left = 0, right = 1
left = 1, right = 1

其中2/3这两点对于单个节点区间有点不好理解，其实是可以处理成为"不选择". 然后再搜索的时候就比较简单，直接选择根节点的最大值。

class Solution:
    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        t = 0
        while (1 << t) < n:
            t += 1
        n = 1 << t

        class Node:
            def __init__(self):
                self.value = [[0] * 2 for _ in range(2)]

            def __repr__(self):
                return str(self.value)

        nodes: List[Node] = [Node() for _ in range(2 * n)]

        def update_once(p):
            c, l, r = nodes[p], nodes[2 * p], nodes[2 * p + 1]
            c.value[0][0] = max(l.value[0][0] + r.value[1][0], l.value[0][1] + r.value[0][0])
            c.value[0][1] = max(l.value[0][0] + r.value[1][1], l.value[0][1] + r.value[0][1])
            c.value[1][0] = max(l.value[1][0] + r.value[1][0], l.value[1][1] + r.value[0][0])
            c.value[1][1] = max(l.value[1][0] + r.value[1][1], l.value[1][1] + r.value[0][1])

        for i in range(len(nums)):
            p = i + n
            np = nodes[p]
            np.value[0][0] = 0
            np.value[0][1] = 0
            np.value[1][0] = 0
            np.value[1][1] = nums[i]

        for p in reversed(range(1, n)):
            update_once(p)

        def update(x, v):
            x = x + n
            nodes[x].value[1][1] = v
            p = x // 2
            while p:
                update_once(p)
                p = p // 2

        def query():
            np = nodes[1]
            return max(np.value[0][0], np.value[0][1], np.value[1][0], np.value[1][1])

        ans = 0
        for p, v in queries:
            update(p, v)
            # print(nodes)
            r = query()
            # print(r)
            ans += r

        MOD = 10 ** 9 + 7
        return ans % MOD