专栏文章

AT_abc423_e [ABC423E] Sum of Subarrays

NN1tr0us_Acid
AT_abc423_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minvpo7k
此快照首次捕获于
2025/12/02 09:08
3 个月前
此快照最后确认于
2025/12/02 09:08
3 个月前
查看原文
vp 的时候一发过的，很显然的前缀和计数。

Solution\texttt{Solution}

首先我们发现，对于每一对 LiL_i 和 RiR_i 来说，只有 AjA_j 满足 Li≤j≤RiL_i \le j \le R_i，这个 AjA_j 才会对答案产生贡献，那么我们可以意识到，如果有一组 (l,r)\left (l,r \right ) 满足 Li≤l≤j≤r≤RiL_i \le l \le j \le r \le R_i，那么 AjA_j 便会对答案产生一次贡献，我们只需要求所有的满足要求的 (l,r)\left (l,r \right ) 的数量即可，很显然一共有 (j−Li+1)×(Ri−j+1)\left (j - L_i + 1 \right ) \times \left (R_i - j + 1 \right ) 组 (l,r)\left (l,r \right ) 满足要求，这里请读者自行思考这个计数。
那么每一个满足 Li≤j≤RiL_i \le j \le R_i 的 AjA_j 对答案的贡献即为
(j−Li+1)×(Ri−j+1)×Aj\left (j - L_i + 1 \right ) \times \left (R_i - j + 1 \right ) \times A_j
把这个式子化开并整理后得到
−j2Aj+(Li+Ri)jAj+(Ri−Li−RiLi+1)Aj-j^2A_j+\left(L_i+R_i\right)jA_j+\left(R_i-L_i-R_iL_i+1\right)A_j
处理一下 AjA_j 和 j×Ajj \times A_j 以及 j2×Ajj^2 \times A_j 三者的前缀和即可。
时间复杂度为 O(n+q)\mathcal O \left( n+q \right)，显然不会超时。

Code\texttt{Code}

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...