競プロ典型90問：010 - Score Sum Queries（★2）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_j?lang=ja

挑戦結果

• 結果：解けた
• 時間：20分ぐらい

考えたこと

• 愚直は計算量がNGなんだろうと思った。累積和なことは思いついた。
• クラスがあるからどう扱えばいいかと思ったけど、それぞれ累積和を持てば良さそう気がついた

公式解説

https://twitter.com/e869120/status/1380652465834532865

解説を読んだふりかえり

• 特になし。★2なのでサクッとときたい。

ソース

N = int(input())
C, P = [], []
for _ in range(N):
    c, p = [int(x) for x in input().split()]
    C.append(c)
    P.append(p)
Q = int(input())
L, R = [], []
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    L.append(l)
    R.append(r)

# 累積和をクラス別に計算する
ruiseki1 = [0] * (N+1)
ruiseki2 = [0] * (N+1)
for i in range(N):
    ruiseki1[i+1] = ruiseki1[i] + (P[i] if C[i]==1 else 0)
    ruiseki2[i+1] = ruiseki2[i] + (P[i] if C[i]==2 else 0)

# print(ruiseki1)
# print(ruiseki2)

for i in range(Q):
    l, r = L[i], R[i]
    ans1 = ruiseki1[r] - ruiseki1[l-1]
    ans2 = ruiseki2[r] - ruiseki2[l-1]
    print(f"{ans1} {ans2}")