算法

(二分，前缀和) $O(T \cdot Q \cdot n \cdot \log (\sum a_i))$

1. 我们不妨先来求 新数组 中第 L 个数是多少。由于新数组中最大的数字就是 $2\cdot 10^8$，我们可以二分查找这个数：假设 mid 是待验证的数，我们可以在线性时间内，求出 原数组 中有多少个连续子区间的和小于等于 mid。如果发现有少于 L 个子区间小于等于 mid，则说明需要取二分的右半部分区间，即 l = mid + 1。否则，r = mid，直到 l == r 为止。
2. 那么如何在线性时间内，求出 原数组 中有多少个连续子区间的和小于等于 mid 呢？这个是双指针应用的经典问题，这里简要说一下思路：对于每个右端点 r，其对应一个最小的左端点 l，满足 [l, r]、[l + 1, r]、……、[r - 1, r] 和 [r, r] 这些闭区间都是小于等于 mid 的连续子区间。在 r 每次向后移动的时候，l 也是单调向后移动的，所以可以做到线性复杂度。
3. 此时，我们分别对 L 和 R 求新数组中的数字，得到 sL 和 sR，即 新数组 中第 L 个数字是 sL，新数组中第 R 个数字是 sR。接下来，我们需要求 新数组 中，第 1 个数字到第 L-1 个数字的区间和，以及第 1 个数字到第 R 个数字的区间和。
4. 现在我们解决求从第 1 个数字到第 L - 1 个数字的区间和。我们首先通过相似的方法求出 原数组 中 子区间和 严格小于 sL 的子区间有多少个，以及子区间和的和。假设我们已经求出来了满足要求子区间的个数 tL.first 和 子区间的总和 tL.second，从第 1 个数字到第 L - 1 个数字的区间和就是 sumL = tL.second + sL * (L - tL.first - 1)。从第 1 个数字到第 R 个数字的区间和就是 sumR = tR.second + sR * (R - tR.first)。
5. 现在我们来求 4 中的问题，刚才我们提到，[l, r]、[l + 1, r]、……、[r - 1, r] 和 [r, r] 这些闭区间都是以 r 为右端点符合条件的区间，这些区间的区间总和怎么求呢？我们首先维护两个前缀和 sum[i] 和 sumx[i]。其中，sum[i] = sum[i - 1] + a[i]，而 sumx[i] = sumx[i - 1] + a[i] * i。连续子区间的个数很好求，每次只需要累加 r - l + 1 即可，而这些子区间和的和，可以通过 sumx[r] - sumx[l - 1] - (sum[r] - sum[l - 1]) * (l - 1) 来求，这个公式可以通过画图的方式进行推导，此处不再赘述。
6. 最终的答案就是 sumR - sumL。

时间复杂度

• 这里单次询问的时间复杂度就是二分的时间套上检查二分 mid 的时间，所以单次询问的时间复杂度为 $O(n \log (\sum a_i))$。

空间复杂度

• 我们只需要前缀和数组即可，故空间复杂度为 $O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

#define LL long long

const int MAXN = 20000010;
const int N = 200010;

int T, n, Q;
int a[N], sum[N];
LL sumx[N];

// 求出原数组中 子区间和 小于等于 x 的数字有多少个。
LL check(int x) {
    LL tot = 0;
    int l = 1;
    for (int i = 1; i <= n; i++) {
        while (l <= i && sum[i] - sum[l - 1] > x)
            l++;
        tot += i - l + 1;
    }
    return tot;
}

// 求出原数组中 子区间和 严格小于 x 的 个数 和 sum。
pair<LL, LL> check_low(int x) {
    LL tot = 0, stot = 0;
    int l = 1;
    for (int i = 1; i <= n; i++) {
        while (l <= i && sum[i] - sum[l - 1] >= x)
            l++;
        tot += i - l + 1;
        stot += sumx[i] - sumx[l - 1] - (LL)(sum[i] - sum[l - 1]) * (l - 1);
    }
    return make_pair(tot, stot);
}

// 求出新数组第 x 个数对应哪个 sum。
int calc(LL x) {
    int l = 1, r = sum[n];
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid) < x)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}

int main() {
    scanf("%d", &T);

    for (int t = 1; t <= T; t++) {

        scanf("%d%d", &n, &Q);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i - 1] + a[i];
            sumx[i] = sumx[i - 1] + a[i] * i;
        }

        printf("Case #%d:\n", t);
        while (Q--) {
            LL L, R;
            scanf("%lld%lld", &L, &R);
            int sL = calc(L);
            int sR = calc(R);

            auto tL = check_low(sL);
            LL sumL = tL.second + sL * (L - tL.first - 1);

            auto tR = check_low(sR);
            LL sumR = tR.second + sR * (R - tR.first);

            cout << sumR - sumL << endl;
        }
    }

    return 0;
}