概要
競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。
※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）
問題010-Score Sum Queries
問題概要
N人の生徒が2つの組に分けられている時、各クラスの学籍番号L~R番の合計点を求める。
これをQ個のクエリにて行う。
解き方
まず初めに、愚直にQ個のクエリ1つ1つに対して、L~R番までの合計を都度求める方法が考えられますが、
この考えでは、L~R番までの合計を求める処理で、最大N回、
これを最大Q回行うと $O(QN)$ となり、TLEになってしまいます。
そこで今回は、累積和を用います。
※累積和について知りたい方はこちらをご確認ください。
そうすると、
１. 各組の累積和Sを求める(N回)
２. Q個のクエリに対して、$S[R]-S[L-1]$を求める。（$O(1)$をQ回）
となり、これは$O(N+Q)$の計算量で十分に高速に求められます。
引用元：競プロ典型90問 Github
実装
answer.py
N = int(input())
# 1組、2組で分けて得点を格納する
c1 = [0]*N
c2 = [0]*N
for i in range(N):
c, p = map(int, input().split())
if c == 1:
c1[i] = p
else:
c2[i] = p
# 各組で累積和 s1, s2を求める
s1 = [0]*(N+1)
s2 = [0]*(N+1)
for i in range(N):
s1[i+1] = s1[i] + c1[i]
s2[i+1] = s2[i] + c2[i]
# Q個のクエリに対し、L~R番までの合計を求める
# L番は和に含めるため、L-1番までの合計をマイナスする
Q = int(input())
for _ in range(Q):
l, r = map(int, input().split())
sum1 = s1[r] - s1[l-1]
sum2 = s2[r] - s2[l-1]
print(sum1, sum2)
最後に
問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）
ここまでお読みいただきありがとうございました。