拆分数组的最小代价

这个题解使用了线段树来优化动态规划的过程。具体思路如下： 1. 定义状态 f[i] 表示将数组 nums[:i] 拆分成若干个非空子数组的最小代价。 2. 状态转移时，对于每个 i，枚举上一个拆分点 j，计算 [j+1,i] 这一段的重要性，加上 f[j] 作为一种拆分方案，取所有方案的最小值作为 f[i] 的值。 3. 朴素的状态转移复杂度为 O(n^2)，因此使用线段树优化，将每次查询 f[j] 的最小值的复杂度降至 O(log n)。 4. 线段树中维护区间加的懒标记，同时在更新答案时，需要对每个数字 x 维护其出现的上一个位置和上上个位置，方便线段树对区间进行修改。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minCost(self, nums: List[int], k: int) -> int:
        # 数组长度
        n = len(nums)
        
        # 线段树的叶子节点数量，取为数组长度的 4 倍，保证是完全二叉树
        mn = [0] * (4 * n)  # 存储区间最小值
        todo = [0] * (4 * n)  # 存储区间加的懒标记

        # 区间加操作，将线段树中节点 o 对应的区间都加上值 v
        def do(o: int, v: int) -> None:
            mn[o] += v
            todo[o] += v

        # 下放懒标记
        def spread(o: int) -> None:
            v = todo[o]
            if v:
                do(o * 2, v)
                do(o * 2 + 1, v)
                todo[o] = 0

        # 更新线段树，将区间 [L,R] 内的值都加上 v
        def update(o: int, l: int, r: int, L: int, R: int, v: int) -> None:
            if L <= l and r <= R:
                do(o, v)
                return
            spread(o)
            m = (l + r) // 2
            if m >= L: update(o * 2, l, m, L, R, v)
            if m < R: update(o * 2 + 1, m + 1, r, L, R, v)
            mn[o] = min(mn[o * 2], mn[o * 2 + 1])

        # 查询线段树，返回区间 [L,R] 内的最小值
        def query(o: int, l: int, r: int, L: int, R: int) -> int:
            if L <= l and r <= R:
                return mn[o]
            spread(o)
            m = (l + r) // 2
            if m >= R: return query(o * 2, l, m, L, R)
            if m < L: return query(o * 2 + 1, m + 1, r, L, R)
            return min(query(o * 2, l, m, L, R),query(o * 2 + 1, m + 1, r, L, R))

        ans = 0
        last = [0] * n  # last[x] 表示数字 x 上一次出现的位置
        last2 = [0] * n  # last2[x] 表示数字 x 上上次出现的位置

        for i, x in enumerate(nums, 1):
            # 更新 f[i] 的值
            update(1, 1, n, i, i, ans)
            
            # 根据 x 的出现情况，对线段树中的区间进行修改
            if last[x]: update(1, 1, n, last2[x] + 1, last[x], 2)
            if last2[x]: update(1, 1, n, 1, last2[x], 1)
            
            # 查询 f[1..i] 的最小值，并加上 k 作为当前的答案
            ans = k + query(1, 1, n, 1, i)
            
            # 更新 x 的上上次出现位置和上次出现位置
            last2[x] = last[x]
            last[x] = i
            
        return ans