BITの総まとめ F#(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
(BITについて)
問題 7 までで、BITの作成が終わりました。
ここでは、総まとめを行いましょう。
class BIT():
def cnt2(self, I): #2で何回割れるか計算する
k = 0
while I % 2 == 0:
k += 1
I = I // 2
return k
def __init__(self, n, A): #BITの作成
self.Tree = [0]* (n + 1) #0で初期化
self.n = n
for i in range(1, n + 1):
k=self.cnt2(i)
for j in range(i - 2 ** k, i): #インデックス注意
self.Tree[i] += A[j]
def add(self, id, x): #A[id]にxを足す作業
self.Tree[id] += x
now = id
while True:
k = self.cnt2(now)
now = now + 2 ** k #親に移動
if now > self.n: #該当するものがないなら根にたどり着いたということ
break
self.Tree[now] += x #加算処理
def sum(self, id): #A[id] までの累積和を計算
ans = 0
#足すべき範囲が0になるまで足し続ける
while id > 0:
ans += self.Tree[id]
id -= 2 ** self.cnt2(id) #すでに足したものを除くため更新
return ans
(問題)
長さ n の配列 A が与えられます。Q 個のクエリが与えられるので順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
n
A_1 A_2 ... A_n
Q
q_1 p_1 X_1
q_2 p_2 X_2
...
q_Q p_Q X_Q- 1 行目には 1 つの整数 n が与えられます。
- 2 行目には n 個の整数 A_1, A_2, ..., A_n が与えられます。
- 3 行目には 1 つの整数 Q が与えられます。
- 3 + i (1 ≦ i ≦ Q) 行目には 3 つの整数 q_i, p_i, X_i が与えられます。
- 入力は合計 3 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
q_i = 2 となる i の個数を T としたとき答えを T 行で出力してください。
j (1 ≦ j ≦ T) 行目には、q_i = 2 となるクエリの中で前から j 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ n ≦ 200000
- 1 ≦ A_i ≦ 10 ^ 9 (1 ≦ i ≦ n)
- 1 ≦ Q ≦ 200000
- 1 ≦ q_i ≦ 2 (1 ≦ i ≦ Q)
- 1 ≦ p_i ≦ n (1 ≦ i ≦ Q)
- q_i = 1 のとき、1 ≦ X_i ≦ 10 ^ 9 (1 ≦ i ≦ Q)
- q_i = 2 のとき、X_i = 0 (1 ≦ i ≦ Q)
- q_i = 2 となる i が 1 つは存在する。
- 入力例1
-
10
2 7 1 8 2 8 1 8 2 8
10
2 5 0
2 10 0
2 1 0
1 6 10
2 5 0
2 10 0
1 1 9
1 3 8
2 1 0
2 5 0
- 出力例1
-
20
47
2
20
57
11
37
