[2023四校联考3]meirin
题意
给出两个序列 \(a,b\)，\(b\) 需要支持区间加。
每次修改完后求：
\[\sum_{l=1}^n\sum_{r=l}^n(\sum_{i=l}^{r}a_i)\times (\sum_{i=l}^{r}b_i) \bmod 10^9+7 \]思路
发现 \(a\) 没有修改，考虑把 \(a\) 作为 \(b\) 的系数单独计算。
把原式变为：
\[\sum_{i=1}^{n} b_i\times (\sum_{l=1}^{i} \sum_{r=i}^{n}\sum_{j=l}^{r}a_j) \]注意 \(l,r\) 必须把 \(i\) 包含入内。
内层枚举可使用前缀和优化，令前缀和序列为 \(A\)。
\[\sum_{i=1}^{n} b_i\times (\sum_{l=1}^{i} \sum_{r=i}^{n}A_r-A_{l-1}) \]发现 \(A_r\) 和 \(A_{l-1}\) 只与 \(l\) 和 \(r\) 中的一个有关，考虑把求和拆成两部分：
\[\sum_{i=1}^{n} b_i\times (i \times \sum_{r=i}^{n}A_r-(n-i+1)\times\sum_{l=1}^{i}a_{l-1}) \]发现前半部分是前缀和的后缀和，后半部分是前缀和的前缀和。
预处理出来可以求出 \(b_i\) 的系数。
初始不带修改的答案可以用：\(\sum_{i=1}^{n} b_i\times k_i\) 求出。
考虑如何修改。
把 \([l,r]\) 增加 \(v\) 时，对答案造成的贡献为：
\[\sum_{i=l}^{r}v\times k_i \]\(v\) 是常数，提出来后为：
\[v\times \sum_{i=l}^r k_i \]求出 \(k_i\) 的前缀和即可优化至每次 \(O(1)\) 修改。
时间复杂度：\(O(n+q)\)。
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
const ll mod = 1e9 + 7;
int n, Q;
ll k[N], h[N], a[N], b[N], kk[N], ans, q[N];
int main() {
freopen("meirin.in", "r", stdin);
freopen("meirin.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> Q;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
a[i] += a[i - 1], a[i] %= mod;
}
for (int i = 1; i <= n; i ++)
cin >> b[i];
for (int i = n; i >= 1; i --)
h[i] = h[i + 1] + a[i], h[i] %= mod;
for (int i = 1; i <= n; i ++)
q[i] = q[i - 1] + a[i], q[i] %= mod;
for (int i = 1; i <= n; i ++)
k[i] = -(n - i + 1) * q[i - 1] + h[i] * i, k[i] %= mod;
for (int i = 1; i <= n; i ++)
kk[i] = kk[i - 1] + k[i], kk[i] %= mod;
for (int i = 1; i <= n; i ++)
ans += b[i] * k[i], ans %= mod;
while (Q --) {
int l, r, v;
cin >> l >> r >> v;
ans += v * (kk[r] - kk[l - 1]);
ans = (ans % mod + mod) % mod;
cout << ans << "\n";
}
return 0;
}