abc423 E - Sum of Subarrays

题意：求 $\sum_{L \le l \le r \le R} a_i$。

通过贡献法，转化为 $\sum_{L \le l \le i \le r \le R} {a_i} = \sum_{i \in[L, R]}{a_i} \times \sum_{L \le l \le r \le R}{[l \le i \le r]}$。

分析一下， $\sum_{i \in [L, R]}a_{i} \times [i - L + 1] \times [R - i + 1]$，整理得到：

因为只有查询，前缀和维护 $\sum a_i \cdot i^2, \sum a_i \cdot i, \sum a_i$ 即可。

P12894 [蓝桥杯 2025 国 Java B] 智能交通信号灯

题意：修改 $a_i$ 和多次查询 $\sum_{l \le i< j \le r}{\text{mex}(a_i, a_j)}$。

通过贡献法，转化为： $\sum_{1 \le m \le 3}{m} \times \sum_{l \le i \lt j \le r}{[\text{mex}(a_i, a_j) = m]}$。

分析一下，记 $[l, r]$ 中， $a_i = 1$ 的个数为 $cnt_1$， $a_i = 2$ 的个数为 $cnt_2$， $a_i = 3$ 的个数为 $cnt_3$。答案为：

P2221 [HAOI2012] 高速公路

题意：区间加 $x$ 和多次查询 $\frac{\sum_{L \le l \le r \le R}\sum_{i \in [l, r]}{a_i}}{\binom{R - L + 1}{2}}$（这里线段转换为点，经过 r - 1 处理）。

观察分子，通过贡献法，转化为： $\sum_{i\in [L, R]}{a_i} \times \sum_{L \le l \le r \le R}{[l \le i \le r]}$。

分析一下， $\sum_{i \in [L, R]} a_i \times [(i - L + 1) \times (R - i + 1)]$，整理得到：

同 abc423 E - Sum of Subarrays，但是有区间修改，用线段树维护 $\sum a_i \cdot i^2, \sum a_i \cdot i, \sum a_i$。

P10403 「XSOI-R1」跳跃游戏

题意：按照下面义 $\text{socre}({x, y})$，求 $\sum_{1 \le x \le y \le n}{\text{score}({x, y})}$。

通过贡献法，答案转化为：

根据区间 $\gcd$ 具有单调性，枚举左端点 $x$，两次二分右端点 $y$，用求和公式算出答案。

（这道题用时限 $750$ ms 情况下，线段树时间复杂度 $O(n \log ^ 2 n)$ 会 TLE 获得 50 pts。正解 ST 表，时间复杂度 $O(n \log n)$）

P5094 [USACO04OPEN] MooFest G 加强版

题意：给两个数组 $v, x$，求 $\sum_{1 \le i, j \le n} \max(v_i, v_j) \cdot |x_i - x_j|$。

按照 $v$ 排序，转化为 $\sum_{i \le i < j \le n} v_j \cdot |x_i - x_j|$。

对 $|x_i - x_j|$ 分类讨论

合并一下

算 $\sum_{1 \le i \lt j \le n, x_j > x_i}{1} - \sum_{1 \le i \lt j \le n, x_j \lt x_i}{1}$ 即：比 $x_j$ 大的数量 $-$ 比 $x_i$ 小的数量；算 $\sum_{i \le i < j \le n, x_j < x_i} x_i - \sum_{i \le i < j\le n, x_j > x_i} x_i$ 即：比 $x_j$ 小的和 $-$ 比 $x_j$ 大的和。用两个线段树维护即可。时间复杂度 $O(n \log n)$。