菜王的 blog

考虑值域从小往大扫，同时维护另一个序列 $b$，扫过的地方 $b$ 对应的位置改成 $1$，那么一对位置 $(i, k) \ (a_i = a_k)$ 的贡献是 $b_{i \sim k}$ 的和。

显然每种 $a_i$ 对应的位置对 $(i, k)$ 贡献是独立的，那么我们只考虑一种。假设这种数 $x$ 的出现次数为 $C$，出现位置分别为 $p_{1 \sim C}$，设 $b_{p_i \sim p_{i + 1}}$ 的和为 $c_i$。

我们有两种方法统计这种贡献：

1. 暴力拆出 $C^2$ 个位置对，变为二维偏序。它的优点在于可以和其他贡献一起跑。
2. $O(n)$ 预处理后给每个询问 $O(1)$ 计算贡献。具体来说，对于区间 $[L, R]$ 的询问，我们找到 $L, R$ 对应的关键点 $p_l, p_r$，那么这个询问对应的贡献是 $\sum_{i = l}^{r - 1} c_i(i - l + 1)(r - i)$。预处理出 $c_i, i \times c_i, i^2 \times c_i$ 的前缀和即可 $O(1)$ 查询。找关键点的时候不能二分，也需要 $O(n)$ 预处理出来。

设置阈值 $B$，$C \le B$ 时用第一种方法，$C > B$ 时用第二种方法。后者的总时间复杂度显然是 $O(\frac nB(n + q))$，前者可以平衡一下做到 $O(nB + q\sqrt n)$。解出 $B = \sqrt n$ 时总时间复杂度为 $O((n + q)\sqrt n)$。因为要扫描线所以不支持强制在线，被莫队做法打爆了。