题意

给出整数数组 $a_1,a_2,...,a_n$ ，求q次，每次给 $l,r(l \leq r)$ ，求 $\sum_{i=l}^{r}\sum_{j=i+1}^{r}a_i*a_j$ 。答案对1,000,000,007取模

题解

做法一

每次询问暴力求解。复杂度 $O(qn^2)$ ，不可接受。预计通过0%。

做法二

考虑对做法一进行优化，如果每次询问只枚举i，剩下的 $\sum_{j=i+1}^{r}a_i*a_j=a_i*\sum_{j=i+1}^{r}a_j$ 。这部分可以预处理出a的前缀和sum(即sum[i]=a[1]+...+a[n])， $O(1)$ 内查询。
复杂度 $O(qn)$ 。预计通过30%。

做法三

观察到 $(\sum_{i=l}^{r}a_i)^2 = \sum_{i=l}^{r}a_i^2 + 2\sum_{i=l}^{r}\sum_{j=i+1}^{r}a_i*a_j$ ，所以 $\sum_{i=l}^{r}\sum_{j=i+1}^{r}a_i*a_j = \frac{(\sum_{i=l}^{r}a_i)^2 - \sum_{i=l}^{r}a_i^2}{2}$ 。
那么可以预处理 $a_1,...a_n$ 的前缀和和 $a_1^2,...,a_n^2$ 的前缀和，每次询问 $O(1)$ 内查询。
复杂度 $O(n+q)$ 。预计通过100%。

代码

#include <bits/stdc++.h>
#define ll long long
const int maxn = 100100;
const int mod = 1000000007;
class Solution {
public:
    /**
     * 多次求交叉乘
     * @param a int整型vector a1,a2,...,an
     * @param query int整型vector l1,r1,l2,r2,...,lq,rq
     * @return int整型vector
     */
    ll s[maxn], s2[maxn];
    vector<int> getSum(vector<int>& a, vector<int>& query) {
        int n = a.size();
        int q = query.size()/2;
        s[0]=s2[0]=0;
        for (int i=1;i<=n;i++) {
            s[i]=s[i-1]+a[i-1];
            s2[i]=s2[i-1]+a[i-1]*(ll)a[i-1];
        }
        vector <int> ret;
        for (int i=1;i<=q;i++) {
            int l=query[2*i-2], r=query[2*i-1];
            ll ans = ((s[r]-s[l-1])*(s[r]-s[l-1])-(s2[r]-s2[l-1]))/2;
            ret.push_back(ans % mod);
        }
        return ret;
    }
};

[题解]交叉乘

题意

题解

做法一

做法二

做法三

代码