ABC 典型90問 010(★2)[累積和]

010 - Score Sum Queries（★2）

■要約

　生徒は2クラスあって，各クラスのある区間のテストの点数の和を求める問題．まず，①各生徒のテストの点数の保持の仕方に工夫がいる．最初は辞書とかがいいのかと思ったがいつか解いた問題で使った，N個の長さの配列を2つ用意してi番目に得点を代入すればよいことが思いついた．次にQ個のクエリについて，毎回指定範囲の和を求めると計算量がO(NQ)でTLEしてしまうことに気がついた．今回はある区間の総和を求めればよいので②累積和を使うことに気がついた．コードは少し冗長になったが以下のようである

N = int(input())
C_1 = [0] * N
C_2 = [0] * N
S_1 = [0] * N
S_2 = [0] * N 
#①得点の記録
for i in range(N):
 c, p = map(int,input().split())
 if c == 1:
   C_1[i] = p
 else:
   C_2[i] = p
#②累積和の計算
S_1[0] = C_1[0]
for i in range(N-1):
 S_1[i+1] = S_1[i] + C_1[i+1]
S_2[0] = C_2[0]
for i in range(N-1):
 S_2[i+1] = S_2[i] + C_2[i+1]
print(S_1)
print(S_2)
Q = int(input())
for j in range(Q):
 l, r = map(int, input().split())
 sum_1 = 0
 sum_2 = 0
 if l == 1:
   sum_1 = S_1[r-1]
   sum_2 = S_2[r-1]
 else:
   sum_1 = S_1[r-1] - S_1[l-2] 
   sum_2 = S_2[r-1] - S_2[l-2]
 print(sum_1, sum_2)