【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();}
};