题目描述

小美拿到了一个数组，她希里你求出所有区间众数之和，你能帮帮她吗?

定义区间的众数为出现次数最多的那个数，如果有多个数出现次数最多，那么众数是其中最小的那个数。

题目思路

​ 对于这题，我们可以将1视为 -1，2 视为 1，那么区间 $[l, r]$ 的和就相当于区间中 2 的数量减去 1 的数量，如果该区间的和 > 0，则说明对于区间 $[l, r]$ 而言，区间的众数为 2 ，否则为 1 。

​ 为了区间和的计算方便，这里采用前缀和来进行处理:

• 记 $s[i]$ 为前 $i$ 个数的和，那么区间 $[l, r]$ 的和可以表示为: $s[r] - s[l - 1]$

​ 将本题转换为，对于每个位置 $r$，找到其左侧所有满足 $s[r] - s[l] > 0，l \in [1, r - 1]$ 的数量