本文共 1973 字，大约阅读时间需要 6 分钟。
据我所知有两种做法,思维难度都不大.
Ⅰ . Ⅰ. Ⅰ.
∑ i = l r ∑ j = i + 1 r a i ∗ a j \sum\limits_{i=l}^{r}\sum\limits_{j=i+1}^{r}a_i*a_j i=l∑rj=i+1∑rai∗aj
= ∑ i = l r a [ i ] ∗ ( p r e [ r ] − p r e [ i ] ) =\sum\limits_{i=l}^{r}a[i]*(pre[r]-pre[i]) =i=l∑ra[i]∗(pre[r]−pre[i])
= p r e [ r ] ∗ ∑ i = l r a [ i ] − ∑ i = l r p r e [ i ] ∗ a [ i ] =pre[r]*\sum\limits_{i=l}^{r}a[i]-\sum\limits_{i=l}^{r}pre[i]*a[i] =pre[r]∗i=l∑ra[i]−i=l∑rpre[i]∗a[i]
这样,维护一个 p r e [ i ] pre[i] pre[i]数组,也就是 a i a_i ai的前缀和
维护一个 p r e [ i ] ∗ a [ i ] pre[i]*a[i] pre[i]∗a[i]的前缀和
这样可以 O ( 1 ) O(1) O(1)计算答案
typedef long long ll;const ll mod = 1e9+7;const int maxn = 2e5+10;class Solution { public: long long pre[maxn],mul[maxn],w[maxn]; vector getSum(vector & a, vector & query) { int n = a.size(); for(int i=0;i Ⅱ.
∑ i = l r ∑ j = i + 1 r a i ∗ a j \sum\limits_{i=l}^{r}\sum\limits_{j=i+1}^{r}a_i*a_j i=l∑rj=i+1∑rai∗aj
= 1 2 ∗ ∑ i = l r ∑ j = l r a i ∗ a j − ∑ i = l r a i 2 =\frac{1}{2}*\sum\limits_{i=l}^{r}\sum\limits_{j=l}^{r}a_i*a_j-\sum\limits_{i=l}^{r}a_i^2 =21∗i=l∑rj=l∑rai∗aj−i=l∑rai2
这样就更加简单
typedef long long ll;const int N = 1e5 + 10, mod = 1e9 + 7;class Solution { public: ll sum1[N], sum2[N], n; vector getSum(vector & a, vector & query) { // write code here n = a.size(); for(int i = 1; i <= n; i++) { sum1[i] = (sum1[i - 1] + a[i - 1]) % mod; sum2[i] = (sum2[i - 1] + 1l * a[i - 1] * a[i - 1] % mod) % mod; } vector ans; for(int i = 0; i < query.size(); i += 2) { int l = query[i], r = query[i + 1]; ll sum = (sum1[r] - sum1[l - 1]) * (sum1[r] - sum1[l - 1]) % mod; sum -= sum2[r] - sum2[l - 1]; ans.push_back(((sum % mod * 500000004) % mod + mod) % mod); } return ans; }}; 转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110248207 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
