25.6.6 闲话：普及组问题
喵仔牛奶
·
·
算法·理论
给定序列 \{a_n\},\{c_n\}，每次单点加上 y，设 b 为 a 从小到大排序的结果，求 \sum_{i=1}^{n}b_ic_i。
考虑：
\begin{aligned}
\sum_{i=1}^{n}b_ic_i=&\sum_{i=1}^{n}\sum_{j=1}^{v}[b_i\ge j]c_i\\
=&\sum_{j=1}^{v}\sum_{i=1}^{n}[b_i\ge j]c_i
\end{aligned}
由于 b 单调不降，每次满足 b_i\ge j 的是一个后缀。因此设 f_i=\sum_{j=n-i+1}^nc_j，有：
\begin{aligned}
\sum_{j=1}^{v}\sum_{i=1}^{n}[b_i\ge j]c_i=\sum_{j=1}^{v}f_{\sum_{i=1}[b_i\ge j]}
\end{aligned}
维护 t_i=\sum_{j=1}^{n}[b_j\ge i] 以及 \sum_{i=1}^{v}f_{t_i}。每次修改只有 \lvert y\rvert 个 t_i 改变，由于 \sum\lvert y\rvert\le 10^7，直接维护即可。
复杂度 \mathcal O(n+q+\sum\lvert y\rvert)。