title
给你一个下标从 0 开始的整数数组 nums 。
nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < ... < ik-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：
- 对于范围
[1, k - 1]内的所有j，nums[ij] - nums[ij-1] >= ij - ij-1都成立。
nums 长度为 1 的 子序列 是平衡的。
请你返回一个整数，表示 nums 平衡 子序列里面的 最大元素和 。
一个数组的 子序列 指的是从原数组中删除一些元素（也可能一个元素也不删除）后，剩余元素保持相对顺序得到的 非空 新数组。
示例 1：
输入：nums = [3,3,5,6]
输出：14
解释：这个例子中，选择子序列 [3,5,6] ，下标为 0 ，2 和 3 的元素被选中。
nums[2] - nums[0] >= 2 - 0 。
nums[3] - nums[2] >= 3 - 2 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
包含下标 1 ，2 和 3 的子序列也是一个平衡的子序列。
最大平衡子序列和为 14 。
示例 2：
输入：nums = [5,-1,-3,8]
输出：13
解释：这个例子中，选择子序列 [5,8] ，下标为 0 和 3 的元素被选中。
nums[3] - nums[0] >= 3 - 0 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
最大平衡子序列和为 13 。
示例 3：
输入：nums = [-2,-1]
输出：-1
解释：这个例子中，选择子序列 [-1] 。
这是一个平衡子序列，而且它的和是 nums 所有平衡子序列里最大的。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109
solution
最大非递减子序列和。
O(nlogn)
线段树维护前面的最大子序列和。每次找小于当前元素的最大子序列和。
需要先离散化，卡常。
'''
线段树
'''
MOD = int(1e9 + 7)
INF = float('inf')
import sortedcontainers
import bisect
import heapq
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
# len = 12
d = []
n = len(nums)
l = INF
r = float('-inf')
for i in range(n):
if nums[i] > 0:
# l = min(l, nums[i] - i)
# r = max(r, nums[i] - i)
d.append((nums[i] - i, nums[i]))
if not d:
return max(nums)
seg = SegmentTree(SegOpCollect.Collect_Max, SegOpUpdate.Update_SetVal, default_val=0)
diff2index = {}
x = sorted(set([v[0] for v in d]))
for v in x:
diff2index[v] = len(diff2index)
# print(d)
# print(diff2index)
l, r = 0, len(diff2index)
# len = 12
seg.build(left=l, right=r)
for v in d:
t = seg.query_interval(l, diff2index[v[0]])
seg.set_point(diff2index[v[0]], t + v[1])
return seg.query_interval(l, r)