题目描述
难度分:1700
输入T(≤104)表示T组数据。所有数据的n之和≤2×105,q之和≤2×105。
每组数据输入n(1≤n≤2×105)、q(1≤q≤2×105)和长为n的数组a(1≤a[i]≤106)。
定义:
c1=a,
c2=a循环左移一次后的数组,
c3=a循环左移两次后的数组,
依此类推。
把这n个长为n的数组串连起来,得到长为n2的数组b=c1+c2+…+cn。下标从1开始。
然后输入q个询问,每个询问输入两个数L和R(1≤L≤R≤n2)。输出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]=Σij=1a[i]。对于任意一个查询(L,R),要求的其实是ΣRi=1b[i]−ΣL−11b[i],所以只要能求出Σleni=1b[i]就可以了。
首先我们需要知道len的前缀包括多少个完整的a,显然包括c=⌊lenn⌋个完整的a,将答案sum先初始化为sum=c×s[n],最后剩一个长度为cnt=len%n的前缀。然后就要确定这是哪个数组长度为cnt的前缀,算出这个数组cx的x=c%n+1。
- 如果n−x+1≤cnt,还需要给答案加上s[x+cnt−1]−s[x−1]。
- 如果n−x+1>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;
}