【Codeforces】CF 2009 F

Firefly’s Queries

题目描述

Firefly is given an array $a$ of length $n$. Let $c_i$ denote the $i$’th cyclic shift${}^{\text{∗}}$ of $a$. She creates a new array $b$ such that $b=c_1+c_2+\cdots +c_n$ where $+$ represents concatenation${}^{\text{†}}$.

Then, she asks you $q$ queries. For each query, output the sum of all elements in the subarray of $b$ that starts from the $l$-th element and ends at the $r$-th element, inclusive of both ends.

${}^{\text{∗}}$The $x$-th ($1\le x\le n$) cyclic shift of the array $a$ is $a_x,a_{x+1}\dots a_n,a_1,a_2\dots a_{x-1}$. Note that the $1$-st shift is the initial $a$.

${}^{\text{†}}$The concatenation of two arrays $p$ and $q$ of length $n$ (in other words, $p+q$) is $p_1,p_2,...,p_n,q_1,q_2,...,q_n$.

输入格式

The first line contains $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ ($1\le n,q\le 2\cdot 10^5$) — the length of the array and the number of queries.

The following line contains $n$ integers $a_1,a_2,...,a_n$ ($1\le a_i\le 10^6$).

The following $q$ lines contain two integers $l$ and $r$ ($1\le l\le r\le n^2$) — the left and right bounds of the query.

Note that the large inputs may require the use of 64-bit integers.

It is guaranteed that the sum of $n$ does not exceed $2\cdot 10^5$ and the sum of $q$ does not exceed $2\cdot 10^5$.

输出格式

For each query, output the answer on a new line.

样例 #1

样例输入 #1

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

样例输出 #1

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

解法

解题思路

可以发现，每次移动会改变相对位置，但是不会改变大小之和，而相对位置其实就是一个环。

我们可以把数组复制一遍变成环，化环为链，计算一遍前缀和。

而每次询问相当于询问固定的几个环，加上一个不完整的环，这个不完整的环就可以使用之前计算的前缀和来完成。

代码

void solve() {
	int n,q;
	cin >> n >> q;
	vector<int>a(n + 1), prefix(2 * n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		prefix[i] = prefix[i - 1] + a[i];
	}
	int s = prefix[n];
	
	for (int i = 1; i <= n; ++i) {
		prefix[n + i] = prefix[n + i - 1] + a[i];
	}
 
	auto cal = [&](int r)->int{
		int len = r / n, x = r % n;
		int L = len + 1, R = L + x - 1;
		int sum = len * s + prefix[R] - prefix[L - 1];
		return sum;
		};
 
	while (q--) {
		int l, r;
		cin >> l >> r;
		int res = cal(r);
		res -= cal(l-1);
 
		std::cout << res << "\n";
	}
}
 
signed main() {
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
};