题意

给出整数数组，求q次，每次给，求 。答案对1,000,000,007取模

题解

做法一

每次询问暴力求解。复杂度，不可接受。预计通过0%。

做法二

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

做法三

观察到，所以。
那么可以预处理的前缀和和的前缀和，每次询问内查询。
复杂度。预计通过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;
    }
};