先枚举绝对众数是谁，把非绝对众数改成 -1，绝对众数改成 1，那么需要计算的就是和大于 0 的区间数量。这容易通过前缀和然后扫一遍做到单次 \(O(n)\) 总复杂度 \(O(n^2)\)，但不能接受。

注意到当元素个数很小的时候，前缀和构成的折线倾向于一直往下走，只在其中很少的有当前这个数的一部分有一段小波动。考虑利用这个性质进行优化。

不放假设当前扫到第 \(i\) 个元素，前缀和数组是 \(S\)，\(0 \sim i\) 的前缀和最小值是 \(min\)。如果 \(S_{i+1} = min - 1\)，那么 \(i+1\) 为右端点一定没有贡献，且紧跟在它后面的所有 \(-1\) 都一定没有贡献。这个时候可以直接不断往后找找到第一个 \(+1\) 的位置从那里开始算贡献。而 \(S_{i+1} \neq min + 1\) 时直接暴力计算贡献。假设这一部分可以做到单次 \(O(1)\)。考虑它的复杂度。假设 \(S_i = min, S_{i+1} \neq min+1\)，且 \(j\) 是最靠前的位置满足 \(S_j = min+1\)，如果不存在则设它是 \(n+1\)。则 \(i \sim j-1\) 里面至少有 \(\frac{j-i}{2}\) 个 +1，所以这中间暴力扫的复杂度均摊到每个 +1 上就是 \(O(+1\)元素个数\()\) 的，所有的合起来就是 \(O(n)\) 的。

维护上有一个稍微复杂的地方就是如何维护这个前缀和。一个暴力方法是维护一个桶表示每个数的出现次数然后每次加减 1 的时候用一个指针在桶上移动维护增量。直接将这个算法移植到上面这个 idea 上有一个问题：\(S_{i+1} = min - 1\) 的时候后面的一段 -1 需要在桶上打一片标记。这可以用一个前缀和来解决，也可以直接不在桶里维护 \(0 \sim min\) 的第一次 +1，也就是说桶里的所有元素实际上是真实值减 1，这样一段 1 的移动就不会对桶产生影响了。这样就做到了真正的 \(O(n)\)。