i233 - 加法搶答賽

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個長度為 n 的數列 a，以及 q 個詢問。每個詢問包含兩個數字 L 和 R，要求計算 $\sum_{i=L}^R a_i \cdot (R - i + 1)$。

解題思路

題目要求計算一個區間的加權和。直接計算每個詢問的時間複雜度是 O(n)，對於 q 個詢問，總時間複雜度是 O(n*q)，可能會超時。因此，需要使用前綴和來優化。

首先，計算前綴和 pre[i] = $\sum_{j=1}^i a[j]$。 然後，計算前綴和的再前綴和 pre2[i] = $\sum_{j=1}^i pre[j]$。

對於每個詢問 (L, R)，可以將 $\sum_{i=L}^R a_i \cdot (R - i + 1)$ 轉換為： $\sum_{i=L}^R a_i \cdot (R - i + 1) = \sum_{i=L}^R a_i \cdot R - \sum_{i=L}^R a_i \cdot i + \sum_{i=L}^R a_i$ $= R \cdot \sum_{i=L}^R a_i - \sum_{i=L}^R a_i \cdot i + \sum_{i=L}^R a_i$ $= R \cdot (pre[R] - pre[L-1]) - \sum_{i=L}^R a_i \cdot i + (pre[R] - pre[L-1])$ $= (R+1) \cdot (pre[R] - pre[L-1]) - \sum_{i=L}^R a_i \cdot i$

更進一步，可以利用 pre2[i] 來計算 $\sum_{i=L}^R a_i \cdot (R - i + 1)$。 $\sum_{i=L}^R a_i \cdot (R - i + 1) = pre2[R] - pre2[L-1] - pre[L-1] * (R - L + 1)$

複雜度分析

• 時間複雜度: O(n + q)
• 空間複雜度: O(n)

程式碼

#include <bits/stdc++.h>
#define ll long long
#define mxn 1000005
#define MAXN 1000005
using namespace std;
ll n,m,t,x,y,z,k,a[mxn],b[mxn],pre[mxn],pre2[mxn];
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		pre[i]+=pre[i-1]+a[i];
		pre2[i]+=pre2[i-1]+pre[i];
	}
	scanf("%lld",&m);
	for(ll i=1;i<=m;++i){
		scanf("%lld %lld",&x,&y);
		printf("%lld\n",pre2[y]-pre2[x-1]-pre[x-1]*(y-x+1));
	}
	return 0;
}