ABC233 D - Count Interval (400)
$ i
番目までの累積和を
$ r_{i+1}
として求めておくと、区間
$ [i,j]
の和は
$ r_{j+1} - r_i
になる
累積和を使ってもこのままでは
$ \mathcal{O}(N^2)
代わりに
$ r_{i+1} - r_j = K
となる
$ j (j \lt i)
の数を足せば良い
これはmapを使うと高速に求まる
unordered_mapなら
$ \mathcal{O}(N)
問題:
https://atcoder.jp/contests/abc233/tasks/abc233_d
提出:
https://atcoder.jp/contests/abc233/submissions/28121607
#ABC233
#400pt
#D
#ABC
#AtCoder
#O(N)