对于这题,我们可以将1视为 -1,2 视为 1,那么区间 [l,r] 的和就相当于区间中 2 的数量减去 1 的数量,如果该区间的和 > 0,则说明对于区间 [l,r] 而言,区间的众数为 2 ,否则为 1 。
为了区间和的计算方便,这里采用前缀和来进行处理:
将本题转换为,对于每个位置 r,找到其左侧所有满足 s[r]−s[l]>0,l∈[1,r−1] 的数量
小美拿到了一个数组,她希里你求出所有区间众数之和,你能帮帮她吗?
定义区间的众数为出现次数最多的那个数,如果有多个数出现次数最多,那么众数是其中最小的那个数。
第一行输入一个正整数n,代表数组的大小
第二行输入n个正整数ai,代表数组的元素
1≤n≤2×105
1≤ai≤2
一个正整数,代表所有区间的众数之和。
输入
3
2 1 2
输出
9
说明
[2],[2,1,2],[2]的众数是 2.
[2,1],[1],[1,2]的众数是 1.
因此答案是 9.