解题思路

我们需要统计满足 $1 \le i < j \le n$ 且 $L(i) > R(j)$ 的下标对 $(i,j)$ 的数量，其中：

核心思路：树状数组 + 频数统计

题目内容

小蓝有一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 。

对于下标 $i$ ，定义左累积频数 $L(i)$ 为 $a_i$ 在前缀 $a_1 \dots a_i$ 中出现的次数；对于下标 $j$ ，定义右累积频数 $R(j)$ 为 $a_j$ 在后缀 $a_j \dots a_n$ 中出现的次数。

小蓝想知道有多少对下标 $(i, j)$ 满足 $1 \le i < j \le n$ ，且 $L(i) > R(j)$ 。

序列长度 $n$ 不超过 $10^5$ ，序列中的每个整数均为正数且不超过 $10^9$ 。