問題1

元の問題の代わりに次の問題を考えます。

---

問題：長さ \(N\) の数列 \(A\) が与えられます。以下の \(Q\) 個の質問に答えてください。

• \(A\) の先頭から \(K\) 項目までの総和を求めよ。

---

この問題は「\(A\) の先頭から \(K\) 項目までの総和」を \(S_K\) とすると、 \(S_0=0\)、\(S_i=S_{i-1}+A_i\) となります。よって \(S_1,\ldots,S_N\) の全てを \(O(N)\) で事前に作ることができ、各質問には \(O(1)\) で答えることができます。

問題2

元の問題の代わりに次の問題を考えます。

---

問題：長さ \(N\) の数列 \(A\) が与えられます。数列 \(B\) は \(A\) を無限に繰り返したものです。以下の \(Q\) 個の質問に答えてください。

• \(B\) の先頭から \(K\) 項目までの総和を求めよ。

---

\(q=\left\lfloor\frac{K}{N}\right\rfloor\)、\(r=K\bmod N\) とします。

このとき \(B\) の先頭から \(K\) 項目までは「\(A\) を \(q\) 回繰り返した数列に、\(A\) の \(r\) 項目までをつなげたもの」となります。 よって求める値は問題1の \(S\) を用いて \(qS_N+S_r\) となります。あらかじめ \(S_1,\ldots,S_N\) の全てを \(O(N)\) で事前に作ることで、各質問には \(O(1)\) で答えることができます。

元の問題

元の問題を考えます。

---

問題：長さ \(N\) の数列 \(A\) が与えられます。数列 \(B\) は \(A\) を無限に繰り返したものです。以下の \(Q\) 個の質問に答えてください。

• \(B\) の \(L\) 項目から \(R\) 項目までの総和を求めよ。

---

「\(B\) の \(L\) 項目から \(R\) 項目までの総和」は「\(B\) の先頭から\(R\) 項目までの和」から「\(B\) の先頭から \(L-1\) 項目までの和」を引くことで求めることができます。よって問題2を2回解くことで求めることができ、質問全体に \(O(N+Q)\) で答えることができます。