题解：区间颜色贡献乘积和

问题转化

给定两个区间 $[l_1, r_1]$ 和 $[l_2, r_2]$，设 $c_1(x)$ 为值 $x$ 在第一个区间出现的次数，$c_2(x)$ 为值 $x$ 在第二个区间出现的次数，求：

$$\sum_{x} c_1(x) \cdot c_2(x)$$

关键推导

1. 公式展开

设 $[l_1, r_1] = A$，$[l_2, r_2] = B$。

$$\text{ans} = \sum_{x} \left( \sum_{i \in A} [a_i = x] \right) \cdot \left( \sum_{j \in B} [a_j = x] \right) $$

交换求和顺序：

$$\text{ans} = \sum_{i \in A} \sum_{j \in B} [a_i = a_j] $$

2. 转化为平面计数

将每个位置 $i$ 视为二维平面上的点 $(i, i)$，原问题变为：
计算矩形 $[l_1, r_1] \times [l_2, r_2]$ 中，满足 $a_i = a_j$ 的点 $(i, j)$ 的数量。

3. 莫队二次离线

标准莫队一次只能处理一个区间，这里需要同时处理两个区间。
注意到：

$$\sum_{i \in A} \sum_{j \in B} [a_i = a_j] = f(r_1, r_2) - f(l_1-1, r_2) - f(r_1, l_2-1) + f(l_1-1, l_2-1) $$

其中 $f(u, v) = \sum_{i=1}^u \sum_{j=1}^v [a_i = a_j]$。

于是问题转化为：快速计算 $f(u, v)$ 对任意 $u, v$ 的查询。

4. 二维数点优化

对每个值 $x$，设它出现的位置为 $p_1, p_2, \dots, p_m$。
在 $f(u, v)$ 中，值 $x$ 的贡献为：

$$\text{cnt}_u(x) \cdot \text{cnt}_v(x)$$

其中 $\text{cnt}_u(x)$ 是 $x$ 在 $[1, u]$ 中出现的次数。

维护 $\text{cnt}_u(x)$ 需要 $O(N)$ 空间，但 $N \le 50000$，可以接受。

5. 分块预处理

将序列分块，块大小为 $B \approx \sqrt{N}$。

预处理：

• $pre[i][x]$：前 $i$ 块中值 $x$ 的出现次数（$i$ 从 0 到块数）
• $f_{block}(i, j)$：第 $i$ 块到第 $j$ 块之间的答案（只考虑整块）

6. 查询处理

对于查询 $f(u, v)$：

1. 令 $u$ 所在块为 $L$，$v$ 所在块为 $R$
2. 整块贡献从预处理 $f_{block}$ 获取
3. 剩余零散部分暴力枚举，用桶临时计数

7. 算法步骤

1. 读入序列，离散化（$a_i \le N$ 但可能稀疏）
2. 分块，预处理 $pre$ 和 $f_{block}$
3. 对每个询问 $(l_1, r_1, l_2, r_2)$：
   • 用二维前缀和公式拆成 4 个 $f(u, v)$ 查询
   • 对每个 $f(u, v)$ 用分块方法计算
   • 合并得到答案

8. 复杂度分析

• 预处理：
  • $pre$ 数组：$O((N/B) \cdot N)$ 空间 $O(N \cdot N/B)$，用哈希表可优化
  • $f_{block}$：$O((N/B)^2 \cdot B)$
• 单次查询：$O(B)$
• 总复杂度：$O(N^{1.5} + Q \sqrt{N})$

取 $B = \sqrt{N} \approx 224$，实际可行。

9. 优化实现

• 使用数组代替哈希表，因为值域 $\le N$
• 注意内存使用，可只存整块间的答案矩阵
• 零散部分用临时数组计数

10. 最终答案

对每个询问输出合并后的结果即可。

此方法在 $N, Q \le 50000$ 的数据范围内可以在 $4$ 秒内通过。