扫描线和贡献法

abc423 E - Sum of Subarrays

题意：求 。

通过贡献法，转化为 。

分析一下，，整理得到：

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

因为只有查询，前缀和维护 即可。

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

题意：修改 和多次查询 。

通过贡献法，转化为：。

分析一下，记 中， 的个数为 ， 的个数为 ， 的个数为 。答案为：

$$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] 高速公路

题意：区间加 和多次查询 （这里线段转换为点，经过 r - 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，但是有区间修改，用线段树维护 。