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]，整理得到：

(-1) \sum{a_i \cdot i^2 + (L + R)\sum{a_i} \cdot i + (R - L - LR + 1) \sum{a_i}}

因为只有查询，前缀和维护 \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。答案为：

1 \times \binom{r - l + 1 - cnt_1}{2} + 2 \times [ \binom{cnt_1}{2}+cnt_1 \cdot (r - l + 1 - cnt_1 - cnt_2)] + 3 \times [cnt_1 \cdot cnt_2]

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)]，整理得到：

(-1) \sum{a_i \cdot i^2 + (L + R)\sum{a_i} \cdot i + (R - L - LR + 1) \sum{a_i}}

同 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})}。

\text{score}({x,y}) = \begin{cases} \text{len}, & \gcd(a_x, \dots, a_y) = 2 \\ \text{len}, & \gcd(a_x, \dots, a_y) = 3 \\ 0, & \text{other} \end{cases}

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

\sum_{1 \le x \le y \le n}{(y - x + 1) \cdot [\gcd(a_x, \dots, a_y) = 2]} + \sum_{1 \le x \le y \le n}{(y - x + 1) \cdot [\gcd(a_x, \dots, a_y) = 3]}

根据区间 \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| 分类讨论

v_j \cdot (\sum_{1 \le i < j \le n, x_j > x_i} x_j - \sum_{1 \le i < j \le n, x_j > x_i} x_i) + v_j \cdot (\sum_{1 \le i < j \le n, x_j < x_i} x_i - \sum_{1 \le i < j \le n, x_j < x_i} x_j)

合并一下

v_j \cdot x_j \cdot (\sum_{1 \le i < j \le n, x_j > x_i} {1} - \sum_{1 \le i < j \le n, x_j < x_i} {1}) + v_j \cdot (\sum_{1 \le i < j \le n, x_j < x_i} x_i - \sum_{1 \le i < j\le n, x_j > x_i} x_i)

算 \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)。

P2717 寒假作业

题意：给一个数组和一个 k，问有多少区间的平均值不小于 k。