题解

思路

1. 把期望转成连通块统计量

固定一次询问。设一个连通块内能力值之和为 $S$，则该连通块中所有无序点对的乘积和为

$$\frac{S^2-\sum a_i^2}{2}.$$

记当前所有连通块的 $S^2$ 之和为 $F$，并记常量 $C=\sum_{i=1}^n a_i^2$。全部连通点对的伤害和是 $(F-C)/2$，而点对总数是 $n(n-1)/2$，所以答案为

$$(F-C)\cdot (n(n-1))^{-1}\pmod {10^9+7}.$$

并查集合并两个块时，若其能力值和分别为 $x,y$，那么 $F$ 增加

$$(x+y)^2-x^2-y^2=2xy.$$

因此只要维护每个根的能力值和，就能在一次合并中 $O(1)$ 更新统计量。

做法

2. tiny：逐次重建并查集

对每个询问新建并查集，依次加入 $l\sim r$ 的边，再套用上式。

• 时间复杂度：$O(q(n+m)\alpha(n))$；
• 空间复杂度：$O(n+m+q)$。

这也是小规模 Oracle。

3. star：星形关系前缀和

特殊性质保证第 $i$ 条边为 $(1,i+1)$。询问 $[l,r]$ 只会产生一个非平凡连通块：中心 $1$ 与叶子 $l+1,\ldots,r+1$。

对叶子能力值及其平方分别求前缀和，即可在 $O(1)$ 得到该块的能力值和与平方和，再计算答案。

• 时间复杂度：$O(n+q)$；
• 空间复杂度：$O(n)$。

4. prefix：只增加边

若所有询问都满足 $l=1$，按 $r$ 从小到大排序询问。扫描边序列并把尚未加入的边合并到并查集，即可在每个询问处直接读取 $F$。

• 时间复杂度：$O((n+m+q)\alpha(n)+q\log q)$；
• 空间复杂度：$O(n+m+q)$。

这一层说明了“固定左端点时按右端点增量维护”的核心；满分算法在每个左端点块中复用它。

5. full：按左端点分块与可撤销并查集

取边编号块长 $B$，把询问按 $l$ 所在块分组。考虑左端点块 $[L,R]$。

5.1 短询问

若询问的 $r\le R$，它完全位于一个块内。临时加入 $l\sim r$ 的至多 $B$ 条边，记录答案后撤销。

5.2 跨块询问

把跨块询问按 $r$ 递增排序。并查集中永久保留 $R+1\sim r$ 的边；每次询问再临时加入 $l\sim R$ 的至多 $B$ 条边，记录答案后只撤销这些临时合并。

并查集不做路径压缩，只按大小合并。每次合并把两个根原先的父亲、块和及全局统计量压入栈；回滚到快照时逆序恢复。永久部分不会被撤销。

5.3 正确性证明

对短询问，快照之后加入的边集合恰为 $[l,r]$，所以并查集连通划分与询问图相同。

对跨块询问，处理到右端点 $r$ 时，永久部分恰为 $[R+1,r]$；临时部分恰为 $[l,R]$。二者并集不重不漏，正好是 $[l,r]$。回滚只删除临时部分，因此不会破坏后续右端点递增所需的永久状态。

并查集每次合并都按 $2xy$ 更新 $F$，所以由第 1 节公式得到的值就是当前询问的伤害期望。算法正确。

5.4 复杂度

复杂度

共有 $O(m/B)$ 个左端点块。扫描永久右侧边以及临时加入块内边的总复杂度为

$$O\left(\left(\frac{m^2}{B}+qB\right)\log n+q\log q+n+m\right).$$

其中 $\log n$ 来自不做路径压缩、只按大小合并的并查集查找。取 $B\approx m/\sqrt q$，可写成 $O(m\sqrt q\log n+q\log q+n)$ 量级；空间复杂度为 $O(n+m+q)$。

标准程序令 $B=\max(1,\lfloor 7m/(5\lfloor\sqrt q\rfloor)\rfloor)$；常数 $7/5$ 只用于平衡永久区间与临时区间的实际开销，且下界 $1$ 保证 $m<\sqrt q$ 时仍有合法分块。若永久边已经使全图连通，后续边不会改变答案，可以直接跳过。独立复核程序反向按右端点分块、让左侧边永久递减加入，使用对称但独立的实现。

6. 易错点

• 兼容表示连通性，不能只统计区间内直接出现的边。
• 自环和重边不会改变连通划分，但必须被输入与回滚逻辑安全处理。
• 分母是 $n(n-1)$，因为分子 $F-C$ 已经把每个无序点对计算了两次。
• 可撤销并查集不能使用路径压缩。