CF2009F.Firefly's Queries

Firefly 有一个长度为 $n$ 的数组 $a$。令 $c_i$ 表示 $a$ 的第 $i$ 次循环移位$^{\text{∗}}$。她创建了一个新数组 $b$，使得 $b = c_1 + c_2 + \dots + c_n$，其中 $+$ 表示拼接$^{\text{†}}$。

接着，她会给你 $q$ 个询问。对于每个询问，输出 $b$ 的从第 $l$ 个元素到第 $r$ 个元素（包括两端）组成的子数组的所有元素之和。

$^{\text{∗}}$ 数组 $a$ 的第 $x$ 次循环移位（$1 \leq x \leq n$）为 $a_x, a_{x+1}, \ldots, a_n, a_1, a_2, \ldots, a_{x-1}$。注意，第 $1$ 次移位就是原始的 $a$。

$^{\text{†}}$ 两个长度为 $n$ 的数组 $p$ 和 $q$ 的拼接（即 $p + q$）为 $p_1, p_2, ..., p_n, q_1, q_2, ..., q_n$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \cdot 10^5$），分别表示数组的长度和询问的数量。

接下来一行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^6$）。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n^2$），表示询问的区间左右端点。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$q$ 的总和不超过 $2 \cdot 10^5$。

对于每个询问，输出一个答案，每行一个。

对于第一个测试用例，$b = [1, 2, 3, 2, 3, 1, 3, 1, 2]$。

由 ChatGPT 4.1 翻译