AT_abc423_e [ABC423E] Sum of Subarrays

N1tr0us_Acid · 2025-09-16 22:50:27 · 题解

vp 的时候一发过的，很显然的前缀和计数。

\texttt{Solution}

首先我们发现，对于每一对 L_i 和 R_i 来说，只有 A_j 满足 L_i \le j \le R_i，这个 A_j 才会对答案产生贡献，那么我们可以意识到，如果有一组 \left (l,r \right ) 满足 L_i \le l \le j \le r \le R_i，那么 A_j 便会对答案产生一次贡献，我们只需要求所有的满足要求的 \left (l,r \right ) 的数量即可，很显然一共有 \left (j - L_i + 1 \right ) \times \left (R_i - j + 1 \right ) 组 \left (l,r \right ) 满足要求，这里请读者自行思考这个计数。

那么每一个满足 L_i \le j \le R_i 的 A_j 对答案的贡献即为

把这个式子化开并整理后得到

处理一下 A_j 和 j \times A_j 以及 j^2 \times A_j 三者的前缀和即可。

时间复杂度为 \mathcal O \left( n+q \right)，显然不会超时。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, q;
const int N = 3e5 + 10;
int a[N];
int sum[N];
int j2sum[N], jsum[N];
signed main(void) {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        jsum[i] = jsum[i - 1] + a[i] * i;
        j2sum[i] = j2sum[i - 1] + a[i] * i * i;
    }
    while (q --) {
        int l, r;
        cin >> l >> r;
        int ans = sum[r] - sum[l - 1];
        ans *= (r - l - l * r + 1);
        ans -= (j2sum[r] - j2sum[l - 1]);
        ans += (l + r) * (jsum[r] - jsum[l - 1]);
        cout << ans << endl; 
    }
    return 0;
}