题意理解 我们有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，表示 $n$ 个居民各自最喜欢的菜。Manlar 可以选择任意区间 $[l, r]$ 邀请居民，并准备该区间内出现次数最多的菜。他获胜的条件是：投给他的票数（即最喜欢这道菜的居民数）严格大于区间长度的一半。

换句话说，我们需要统计所有满足以下条件的区间 $[l, r]$：区间内存在某个菜 $x$，使得 $x$ 的出现次数 $> \frac{r-l+1}{2}$。

核心思路

1.关键转化 对于每个可能的菜 $x$，我们单独考虑：

构造新序列 $b$：

如果 $a_i = x$，则 $b_i = 1$

如果 $a_i \neq x$，则 $b_i = -1$

计算前缀和 $s$：$s_0 = 0$，$s_i = s_{i-1} + b_i$（$1 \le i \le n$）

重要性质：区间 $[l, r]$ 以 $x$ 为绝对众数当且仅当 $s_r > s_{l-1}$。

证明：区间和 $s_r - s_{l-1} = cnt_x \times 1 + (len - cnt_x) \times (-1) = 2cnt_x - len$，其中 $len = r-l+1$。这个值大于 $0$ 等价于 $cnt_x > len/2$。

2.问题转化 对于固定的菜 $x$，我们需要统计满足 $0 \le l-1 < r \le n$ 且 $s_{l-1} < s_r$ 的 $(l, r)$ 对数。

这等价于计算前缀和数组 $s[0 \dots n]$ 的正序对数量（即 $i < j$ 且 $s_i < s_j$ 的 $(i, j)$ 对数）。

算法步骤 预处理：找出序列中所有不同的菜品种类

对每个候选菜 $x$：

构造对应的前缀和数组 $s$

用分治法（类似归并排序）统计 $s$ 数组的正序对数量

累加结果：将所有候选菜对应的正序对数量相加，得到最终答案

复杂度分析

时间复杂度：$O(n \log n)$。虽然我们对每个不同的菜都进行了一次分治计算，但由于每个位置只在对应的菜计算中被设为 $+1$，在其他计算中都是 $-1$，所以总体复杂度保持在 $O(n \log n)$。

空间复杂度：$O(n)$，主要用于存储前缀和数组和临时数组。