题目描述

难度分:$1700$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$q$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$、$q(1 \leq q \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^6)$。

定义：
$c_1=a$，
$c_2=a$循环左移一次后的数组，
$c_3=a$循环左移两次后的数组，
依此类推。
把这$n$个长为$n$的数组串连起来，得到长为$n^2$的数组$b=c_1+c_2+…+c_n$。下标从$1$开始。

然后输入$q$个询问，每个询问输入两个数$L$和$R(1 \leq L \leq R \leq n^2)$。输出$b[L]+b[L+1]+…+b[R]$。

输入样例

5
3 3
1 2 3
1 9
3 5
8 8
5 5
4 8 3 2 4
1 14
3 7
7 10
2 11
1 25
1 1
6
1 1
5 7
3 1 6 10 4
3 21
6 17
2 2
1 5
1 14
9 15
12 13
5 3
4 9 10 10 1
20 25
3 11
20 22

输出样例

18
8
1
55
20
13
41
105
6
96
62
1
24
71
31
14
44
65
15

算法

前缀和

先预处理一个前缀和数组$s$，其中$s[i]=\Sigma_{j=1}^{i}a[i]$。对于任意一个查询$(L,R)$，要求的其实是$\Sigma_{i=1}^{R}b[i]-\Sigma_{1}^{L-1}b[i]$，所以只要能求出$\Sigma_{i=1}^{len}b[i]$就可以了。

首先我们需要知道$len$的前缀包括多少个完整的$a$，显然包括$c = \lfloor \frac{len}{n} \rfloor$个完整的$a$，将答案$sum$先初始化为$sum=c \times s[n]$，最后剩一个长度为$cnt=len \% n$的前缀。然后就要确定这是哪个数组长度为$cnt$的前缀，算出这个数组$c_x$的$x=c \% n + 1$。

1. 如果$n-x+1 \leq cnt$，还需要给答案加上$s[x+cnt-1]-s[x-1]$。
2. 如果$n-x+1 \gt cnt$，还需要给答案加上$s[n]-s[x-1]+s[cnt-(n-x+1)]$。

复杂度分析

时间复杂度

预处理出$s$数组的时间复杂度为$O(n)$。计算每个询问的答案时间复杂度为$O(1)$，总的时间复杂度$O(q)$。

空间复杂度

除去输入的数组$a$，额外空间的瓶颈为$s$数组，它和$a$同规模。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n, q, a[N];
LL s[N];

LL get(LL len) {
    LL cnt = len % n, c = len / n;
    LL sum = c*s[n];
    if(cnt > 0) {
        // 还要加一个cnt个数的前缀，需要确定这是哪个数组的前缀
        int l = c % n + 1;
        if(n - l + 1 >= cnt) {
            int r = l + cnt - 1;
            sum += s[r] - s[l - 1];
        }else {
            sum += s[n] - s[l - 1];
            cnt -= n - l + 1;
            sum += s[cnt];
        }
    }
    return sum;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        while(q--) {
            LL l, r;
            scanf("%lld%lld", &l, &r);
            l--;
            printf("%lld\n", get(r) - get(l));
        }
    }
    return 0;
}