第 370 周赛 100112. 平衡子序列的最大和（困难，离散化，权值树状数组）

在这里插入图片描述
太难了，看答案理解了半天

题目的要求可以理解为 nums[i_j] - i_j >= nums[i_i] - i_i ，所以问题化为求序列 b_i = nums[i] - i 的非递减子序列的最大元素和
需要前置知识，离散化，树状数组
离散化：将分布大却数量少(即稀疏)的数据进行集中化的处理，减少空间复杂度，也就是不关心元素的实际值，只关心元素的大小关系。具体过程就是将原数组排序，以排序后的下标作为原数组的值的”新值“
树状数组就是利用lowbit（最右边的 1 的值 10010 的 lowbit 就是 10）的性质，把n个节点串起来，隐式地构造一棵树（当n不是2幂次时，是一个森林）。每个节点x的父亲是x + lowbit(x)，每个节点维护其子节点的和。
最重要的一点，也是树状数组算法的核心，即处于当前x节点左边不在x子树中最大的节点是x - lowbit(x)
在本题中数组 tree[i] 表示序列末尾为 i 及其它的子节点的非递减子序列的最大元素和，例如 tree[6] 就表示以5或6结尾的非递减子序列的最大元素和
所以只需要遍历 nums，遍历至 nums[i] 时，通过 b[i] 知道 nums[i] 在整个数组中排第几，也就是 nums[i] 将插入树状数组 tree 的哪个位置，举例来说，如果 nums[i] 对应的离散化值为 6，通过那么它可以加入任何以 1，2，…，6 为结尾的非递减子序列，也就 tree[6] 应该更新为 max(tree[j]) + nums[i]（j = 1，2，…，6），而通过第5点我们可以在 O(logn) 的时间复杂度内求出 max(tree[j])，在求得新的 tree[6] 之后还需要更新维护树状数组，即要更新 tree[6] 的所有祖先节点，在这里只有 8

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        b = sorted(set(x - i for i, x in enumerate(nums)))  # 离散化 nums[i]-i
        t = BIT(len(b) + 1)
        ans = -inf
        for i, x in enumerate(nums):
            j = bisect_left(b, x - i) + 1  # nums[i]-i 离散化后的值（从 1 开始）
            f = max(t.pre_max(j), 0) + x
            ans = max(ans, f)
            t.update(j, f)
        return ans

# 树状数组模板（维护前缀最大值）
class BIT:
    def __init__(self, n):
        self.tree = [-inf] * n

    def update(self, i: int, val: int) -> None:
        while i < len(self.tree):
            self.tree[i] = max(self.tree[i], val)
            i += i & -i

    def pre_max(self, i: int) -> int:
        mx = -inf
        while i > 0:
            mx = max(mx, self.tree[i])
            i -= i & -i
        return mx