牛客国庆集训派对Day4 区间权值

对于这种式子 $f(l,r)=(\sum_{i=l}^{r}a_i)\times w_{r-l+1}$ 一般情况下，我们先仿照答案写出前几项，看看有没有规律

定义前缀和 $s_k=\sum_{i=1}^{k}a_i$ ，把要求出的式子 $\sum_{l=1}^{n}\sum_{r=1}^{n}f(l,r)$ 展开来写 $\begin{aligned} =&f(1,1)+f(1,2)+f(1,3)+f(1,4)\dots+f(1,n)+\\ &f(2,2)+f(2,3)+f(2,4)+\dots+f(2,n)+\\ &f(3,3)+f(3,4)+\dots+f(3,n)+\\ &\dots+\\ &f(n,n)\\ =&s_1w_1+s_2w_2+s_3w_3+s_4w_4\dots+s_nw_n+\\ &(s_2-s_1)w_1+(s_3-s_1)w_2+(s_4-s_1)w_3+\dots+(s_n-s_1)w_{n-1}+\\ &(s_3-s_2)w_1+(s_4-s_2)w_2+\dots+(s_n-s_2)w_{n-2}+\\ &\dots+\\ &(s_{n-1}-s_{n-2})w_1+(s_{n}-s_{n-2})w_2+\\ &(s_n-s_{n-1})w_1\\ \end{aligned}$
然后，通过观察发现，可以把每一个列 $w_i$ 相加的值，合并到一起

建议列成一排这样约分一眼就看出来了，每次都是前面空出几项，后面空出几项 $\begin{aligned} s_nw_1=&(s_1+s_2-s_1+s_3-s_2+\dots+s_{n-1}-s_{n-2}+s_{n}-s_{n-1})w_1\\ (s_{n}+s_{n-1}-s_1)w_2=&(s_2+s_3-s_1+s_4-s_2+\dots+s_{n-2}-s_{n-4}+s_{n-1}-s_{n-3}+s_{n}-s_{n-2})w_2\\ (s_n+s_{n-1}+s_{n-2}-s_2-s_1)w_3=&\dots\\ &\dots\\ s_nw_n \end{aligned}$
通过观察式子，我们发现

$w_i$ 对应 $s_n-0$ 加一项 $s_n$ 减去 $0$ 项

$w_2$ 对应 $s_n+s_{n-1}-s_1$ 加两项 $s_n+s_{n-1}$ 减去 $1$ 项

$w_3$ 对应 $s_n+s_{n-1}+s_{n-2}-s_2-s_1$ 加三项 $s_n+s_{n-1}+s_{n-2}$ 减去 $2$ 项

而且这些加的，或者减去的，都是一段区间的数字，也可以用前缀和来优化

定义前缀和 $E_k=\sum^{k}_{i=1}s_i$ ，改写原先的式子，即

$s_nw_1=E_1w_1$

$(s_n+s_{n-1}-s_1)w_2=(E_n-E_{n-2}-E_1)w_2$

$(s_n+s_{n-1}+s_{n-2}-s_2-s_1)w_3=(E_n-E_{n-3}-E_2)w_3$

得到通式 $(E_n-E_{n-i}-E_{i-1})w_i$

然后我们就可以应用两遍前缀和 $O(n)$ 求出答案了

最终式子 $ans=\sum^{n}_{i=1}(E_n-E_{n-i}-E_{i-1})w_i$ ，记得每步都取模

有个细节， $E$ 数组要用 $long long$ 不然在求前缀和的时候会爆掉，因为 $s$ 已经是临界值了， $E$ 和 $s$ 两个相加会先爆掉再取模

#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long LL;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int a[N],w[N],s[N],n;
LL E[N];
int main() {
#ifndef ONLINE_JUDGE
    freopen("D:/scode/in.txt","r",stdin);
    //freopen("D:/scode/out.txt","w",stdout);
#endif
    IO;
    cin >> n;
    for(int i = 1;i <= n; ++i) cin >> a[i];
    for(int i = 1;i <= n; ++i) cin >> w[i];
    // 先对ai 求一遍前缀和
    for(int i = 1;i <= n; ++i) s[i] = (s[i - 1] + a[i]) % mod;
    // 再对si 求一遍前缀和
    for(int i = 1;i <= n; ++i) E[i] = (E[i - 1] + s[i]) % mod;
    // 计算答案
    int ans = 0;
    for(int i = 1;i <= n; ++i) 
        ans = (ans + ((E[n] - E[n - i] - E[i - 1] + mod) % mod * w[i]) % mod) % mod;
    cout << ans << endl;
    return 0;
}