求给定数组所有子数组的MEX之和 需O(n)或O(nlogn)高效解法

• 核心采用贡献法简化计算：所有子数组的MEX之和等价于对每个k≥1，统计MEX≥k的子数组数量，将所有统计值相加。因为MEX为x的子数组会对k=1到k=x各贡献1次，求和结果和直接累加所有子数组MEX完全一致。
• MEX≥k的充要条件是子数组包含0、1、……、k-1的所有整数。
• 遍历数组时维护两个核心变量：last[v]表示数值v最后一次出现的下标，current_mex表示当前遍历到右边界r时，前缀数组[0,r]的MEX。
• 维护递推数组f[k]，表示min{last[0], last[1], ..., last[k-1]}，含义为：以r为右端点时，满足MEX≥k的子数组的左端点最大可取值为f[k]，对应共有f[k]+1个合法左端点。
• 每次更新last[x]后，仅需要从k=x+1开始更新f[k]。由于f[k]是单调不减的，每个f[k]最多被更新O(1)次（分摊），整体时间复杂度为O(n)，可满足n≤1e5的约束要求。

def sum_subarray_mex(arr):
    n = len(arr)
    # 数组元素最大值不超过n，开n+2空间避免越界
    last = [-1] * (n + 2)
    current_mex = 0
    # f[k] = min(last[0], last[1], ..., last[k-1])
    f = [0] * (n + 2)
    sum_f = 0
    ans = 0
    for r in range(n):
        x = arr[r]
        last[x] = r
        # 更新当前前缀的MEX
        while last[current_mex] != -1:
            current_mex += 1
        # 仅当x小于当前mex时才需要更新f数组
        if x < current_mex:
            k = x + 1
            prev = f[k]
            # 计算新的f[k]值
            new_val = last[k-1] if k == 1 else min(f[k-1], last[k-1])
            while k <= current_mex and new_val > prev:
                sum_f += (new_val - prev)
                f[k] = new_val
                k += 1
                if k > current_mex:
                    break
                prev = f[k]
                new_val = min(f[k-1], last[k-1])
        # 累加当前右边界r对应的所有子数组的贡献
        ans += sum_f + current_mex
    return ans

内容的提问来源于stack exchange，提问作者Nitin