数学、前缀和

考虑 $b_i$ 的贡献

$$b_i \times \sum_{l=1}^{n} \sum_{r=l}^{n} [i \in [l,r]] \times \sum\limits_{j=l}^{r} a_j = b_i \times \sum_{l=1}^{i} \sum_{r=i}^{n} \sum\limits_{j=l}^{r} a_j$$

考虑 $a_j$ 的贡献

在 $j \leq i$ 时为

$$a_j \times j \times (n-i+1)$$

在 $j \geq i$ 时为

$$a_j \times i \times (n-j+1)$$

可以合并得到

$$a_j \times \min(i,j) \times \min(n-i+1,n-j+1)$$

定义

$$pre(i) = \sum\limits_{j=1}^{i} a_j \times j \times (n-i+1)$$

定义

$$suf(i) = \sum\limits_{j=i}^{n} a_j \times i \times (n-j+1)$$

于是

$$ans=\sum\limits_{i=1}^{n} b_i \times (pre(i) + suf(i) - a_i \times i \times (n-i+1))$$

同时有

$$pre(i+1)=pre(i) - \sum\limits_{j=1}^{i} a_j \times j + a_{i+1} \times (i+1) \times (n-(i+1)+1)$$

$$suf(i+1)=suf(i) + \sum\limits_{j=i+1}^{n} a_j \times (n-j+1) - a_i \times i \times (n-i+1)$$

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1'000'000'007;
Mint<mod> ans,a[500'005],b[500'005],pre[500'005],suf[500'005],sump[500'005],sums[500'005];
int n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) sump[i]=sump[i-1]+a[i]*i;
    for(int i=n;i>=1;i--) sums[i]=sums[i+1]+a[i]*(n-i+1);
    pre[1]=a[1]*n;
    for(int i=1;i<=n;i++) suf[1]+=a[i]*(n-i+1);
    for(int i=1;i<=n-1;i++){
        pre[i+1]=pre[i]-sump[i]+a[i+1]*(i+1)*(n-(i+1)+1);
        suf[i+1]=suf[i]+sums[i+1]-a[i]*i*(n-i+1);
    }
    for(int i=1;i<=n;i++) ans+=b[i]*(pre[i]+suf[i]-a[i]*i*(n-i+1));
    cout<<ans<<'\n';
    return 0;
}