ABC201~210
https://qiita.com/sano192/items/2efd871a4b2dee05c321
ABC211~220
https://qiita.com/sano192/items/03c27d4316af25bdf645
ABC220~225
https://qiita.com/sano192/items/8fe5e85a5b3fb15bb49b
ARC119 A
提出
# 入力の受け取り
N=int(input())
# 「暫定答え」
ans=10**20
# b=0~59
for b in range(60):
# aを計算
a=N//2**b
# cを計算
c=N-a*2**b
# 「暫定答え」より「a+b+c」が小さければ更新
ans=min(ans,a+b+c)
# 答えを出力
print(ans)
ARC119 B
提出
# 入力の受け取り
N=int(input())
S=input()
T=input()
# 「0」の個数が不一致なら
if S.count("0")!=T.count("0"):
# 「-1」を出力
print(-1)
# 終了
exit()
# 「0」がある場所
S_0=[]
T_0=[]
# i=0~(N-1)
for i in range(N):
# 「0」の位置を記録
if S[i]=="0":
S_0.append(i)
if T[i]=="0":
T_0.append(i)
# 答え
ans=0
# i=0~(S_0の長さ)
for i in range(len(S_0)):
# 一致しないなら
if S_0[i]!=T_0[i]:
# 答えにカウント
ans+=1
# 答えを出力
print(ans)
ARC120 A
提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# Aの累積和
A_cum=[0]*N
# 最初にA[0]を入れておく
A_cum[0]=A[0]
# i=1~(N-1)
for i in range(1,N):
# 「iまでの累積和」=「(i-1)までの累積和」+A[i]
A_cum[i]=A_cum[i-1]+A[i]
# 最大値
m=0
# fの値
f=0
# k=1~(N-1)
for k in range(N):
# k番目までの最大値
# そこまでの最大値よりA[k]が大きければ更新
m=max(m,A[k])
# f+(k+1)*m+「kまでの累積和」
f+=(k+1)*m+A_cum[k]
# 出力
print(f)
# (k+1)*mを引いておく
f-=(k+1)*m
ARC120 B
提出
# 余りの定義
mod=998244353
# 入力の受け取り
H,W=map(int,input().split())
# マス目の記録用リスト
grid=[]
# H回
for i in range(H):
# 受け取り
S=input()
# 1文字ずつリストへ展開
S_list=list(S)
# gridへ記録
grid.append(S_list)
# 距離ごとのマス目の種類を記録するセット
dist=[set() for i in range(H+W)]
# gyou=0~(H-1)
for gyou in range(H):
# retu=0~(W-1)
for retu in range(W):
# 距離=行番号+列番号
dist[gyou+retu].add(grid[gyou][retu])
# 答え
ans=1
# i=0~(H+W)
for i in range(H+W):
# (3)赤と青が混在
if "R" in dist[i] and "B" in dist[i]:
# 「0」を出力
print(0)
# 終了
exit()
# (1)全部色が塗られていないマス=全マスが「.」の場合
elif dist[i]=={"."}:
# 赤か青に統一するから2通り
ans*=2
# 余りを取る
ans%=mod
# 答えの出力
print(ans)
ARC121 A
提出
# 入力の受け取り
N=int(input())
# 座標の格納用
p=[]
# x座標と家の番号の格納用
px=[]
# y座標と家の番号の格納用
py=[]
# N回
for i in range(N):
# 入力の受け取り
x,y=map(int,input().split())
# 座標を記録
p.append([x,y])
# x座標と家の番号を記録
px.append([x,i])
# y座標と家の番号を記録
py.append([y,i])
# チェビシェフ距離の計算
# 引数：p1=[p1のx座標,p1のy座標],p2=[p2のx座標,p2のy座標] → 返り値：チェビシェフ距離
def chebyshev(p1,p2):
return max(abs(p1[0]-p2[0]),abs(p1[1]-p2[1]))
# xの小さい順ソート
px.sort()
# yの小さい順ソート
py.sort()
# 候補となる家の番号格納用
# 重複を避けるためセット
indx=set()
# x座標が1番小さい家の番号
indx.add(px[0][1])
# x座標が2番目に小さい家の番号
indx.add(px[1][1])
# x座標が1番大きい家の番号
indx.add(px[-1][1])
# x座標が2番目に大きい家の番号
indx.add(px[-2][1])
# y座標が1番小さい家の番号
indx.add(py[0][1])
# y座標が2番目に小さい家の番号
indx.add(py[1][1])
# y座標が1番大きい家の番号
indx.add(py[-1][1])
# y座標が2番目に大きい家の番号
indx.add(py[-2][1])
# リストへ変換
indx=list(indx)
# 各家の距離記録用
dist=[]
# i=0~(indxの長さ-1)
for i in range(len(indx)):
# j=(i+1)~(indxの長さ-1)
for j in range(i+1,len(indx)):
# チェビシェフ距離を計算
d=chebyshev(p[indx[i]],p[indx[j]])
# 距離を記録
dist.append(d)
# 降順ソート
dist.sort(reverse=True)
# 2番目を出力
print(dist[1])
ARC121 B
提出
# 入力の受け取り
N=int(input())
# R,G,Bをグループ分け
R=[]
G=[]
B=[]
# 2N回
for i in range(2*N):
# 受け取り(文字列)
a,c=map(str,input().split())
# 割り振り
if c=="R":
R.append(int(a))
elif c=="G":
G.append(int(a))
else:
B.append(int(a))
# 全てのグループが偶数匹なら
if len(R)%2==0 and len(G)%2==0 and len(B)%2==0:
# 答えは「0」
print(0)
exit()
# even：偶数匹グループ
# odd1,odd2：奇数匹グループ
# Rが偶数匹グループ
if len(R)%2==0:
even,odd1,odd2=R,G,B
# Gが偶数匹グループ
elif len(G)%2==0:
even,odd1,odd2=G,R,B
# Bが偶数匹グループ
else:
even,odd1,odd2=B,R,G
# リストの要素について、差の絶対値の最小を計算する関数
# 引数：X.Y(リスト) → 返り値：差の絶対値の最小
def min_d(X,Y):
# ソート
X.sort()
Y.sort()
# 差(difference)
d=10**20
# Xのインデックス
i=0
# Yのインデックス
j=0
# i,jが範囲外にならない限り
while i<len(X) and j<len(Y):
# 差の絶対値を計算し、小さければ更新
d=min(d,abs(Y[j]-X[i]))
# 小さい方のインデックスを進める
if X[i]<Y[j]:
i+=1
elif Y[j]<X[i]:
j+=1
# X[i]=Y[j]なら差は0
else:
return 0
# 差の絶対値の最小を返す
return d
# (1)2匹を一緒に住まわせる
ans=min_d(odd1,odd2)
# (2)さらに偶数匹グループから2匹取り出してそれぞれと住まわせる。
ans=min(ans,min_d(odd1,even)+min_d(odd2,even))
# 答えの出力
print(ans)
ARC122 A
提出
# 余りを定義
mod=10**9+7
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 樹形図における「i列目の「+」の個数」
Plus=[0]*(10**5+10)
# 樹形図における「i列目の「-」の個数」
Minus=[0]*(10**5+10)
# 0列目の「+」の個数=1
Plus[0]=1
# 0列目の「-」の個数=0
Minus[0]=0
# i=0~(10^5+9)
for i in range(1,10**5+10):
# 漸化式のとおりに計算
Plus[i]=Plus[i-1]+Minus[i-1]
Minus[i]=Plus[i-1]
# 余りを取る
Plus[i]%=mod
Minus[i]%=mod
# 「「+」をスタートとして、x列分進んだときの場合の数」
countPlus=[0]*(10**5+10)
# 初期値
countPlus[0]=1
countPlus[1]=2
# x=0~(10^5+9)
for x in range(2,10**5+10):
# 漸化式のとおりに計算
countPlus[x]=countPlus[x-2]+countPlus[x-1]
# 余りを取る
countPlus[x]%=mod
# 「「-」をスタートとして、x列分進んだときの場合の数」
countMinus=[0]*(10**5+10)
# 初期値
countMinus[0]=1
countMinus[1]=1
# x=0~(10^5+9)
for x in range(2,10**5+10):
# 漸化式
countMinus[x]=countMinus[x-2]+countMinus[x-1]
# 余りを取る
countMinus[x]%=mod
# 答え
ans=0
# i=0~(N-1)
for i in range(N):
# +A[i]の係数：「i列目の「+」の個数」*「「+」をスタートとして、((N-1)-i)列分進んだときの場合の数」
ans+=A[i]*Plus[i]*(countPlus[(N-1)-i])
# -A[i]の係数：「i列目の「-」の個数」*「「-」をスタートとして、((N-1)-i)列分進んだときの場合の数」
ans-=A[i]*Minus[i]*(countMinus[(N-1)-i])
# 余りを取る
ans%=mod
# 答えの出力
print(ans)
別解
# 余りを定義
mod=10**9+7
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# フィボナッチ数列の計算
F=[0,1]
for i in range(2,10**5+10):
F.append((F[i-2]+F[i-1]%mod))
# 答え
ans=0
# i=0~(N-1)
for i in range(N):
# +A[i]の係数
ans+=A[i]*F[i+1]*(F[(N+1)-i])
# -A[i]の係数：
ans-=A[i]*F[i]*(F[N-i])
# 余りを取る
ans%=mod
# 答えの出力
print(ans)
ARC122 B
提出
# pypyで提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 期待値計算
# 引数：x → 返り値：x円支払い失う金額の期待値
def E(x):
# 期待値
result=0
# i=0~(N-1)まで
for i in range(N):
# シナリオA[i]が起きた時失う金額
result+=(x+A[i]-min(A[i],2*x))
# 各シナリオの起こる確率=(1/N)を掛ける⇔Nで割る
result/=N
# 値を返す
return result
# 左端
L=0
# 右端
R=max(A)
# 100回
for i in range(100):
# 中央左側
cl=(2*L+R)/3
# 中央右側
cr=(L+2*R)/3
# 中央左側が低いまたは同じ
if E(cl)<=E(cr):
# 右側を更新
R=cr
# 中央右側が低い
else:
# 左側を更新
L=cl
# 答えの出力
print(E(cl))
別解
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# 中央値の計算
from statistics import median
x=median(A)
# xを2で割る
x/=2
# 期待値計算
ans=0
for a in A:
ans+=x+a-min(a,2*x)
ans/=N
# 答えの出力
print(ans)
ARC123 A
提出
# 入力の受け取り
A1,A2,A3=map(int,input().split())
# x,yを計算
x=A2-A1
y=A3-A2
# ・x<y
if x<y:
# x,yの偶奇が同じ
if x%2==y%2:
# 「A2に1加える」を((y-x)/2)回
print((y-x)//2)
# x,yの偶奇が違う
else:
# count：操作回数
# 「A3に1加える」を1回
count=1
# 「A3に1加える」⇔yに+1
y+=1
# 「A2に1加える」を((y-x)/2)回
count+=(y-x)//2
# 操作回数を出力
print(count)
# ・x=y
elif x==y:
# 操作は不要
print(0)
# ・y<x
else:
# 「A3に1加える」を(x-y)回
print(x-y)
ARC123 B
提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
# 小さい順に並び替える
A.sort()
B.sort()
C.sort()
# 条件を満たす組み合わせのカウント
count=0
# 初期値
i,j,k=0,0,0
# インデックスの範囲内の間
while i<N and j<N and k<N:
# B[j]≤A[i]なら
if B[j]<=A[i]:
# 次のjへ
j+=1
# A[i]<B[j]なら
else:
# C[k]≤B[j]なら
if C[k]<=B[j]:
# 次のkへ
k+=1
# B[j]<C[k]なら
else:
# カウントする
count+=1
# 次のi,j,kへ
i+=1
j+=1
k+=1
# 答えの出力
print(count)
ARC124 A
提出
# 余りの定義
mod=998244353
# 入力の受け取り
N,K=map(int,input().split())
# 各カードに書ける整数の種類数
# 最初は全てのカードに「1」「2」...「K」のK種類が書ける
cards=[K]*(N+1)
# i=1~N
for i in range(1,K+1):
# 入力を文字列で受け取り
c,k=map(str,input().split())
# kを整数へ変換
k=int(k)
# k番目のカードには「i」しか書けない
cards[k]=1
# i=1~(N-1)
for i in range(1,N):
# c=「R」
if c=="R":
# (k+i)<(N+1)未満なら(インデックスの範囲外でなければ)
if k+i<N+1:
# cards[k+i]が1でなければ
if 1!=cards[k+i]:
# 「i」が書けなくなる⇔書ける種類が一つ減る
cards[k+i]-=1
# (k+i)=(N+1)なら
else:
# 次のiへ
break
# c=「L」
else:
# 0<(k-i)なら
if 0<k-i:
# cards[k-i]が1でなければ
if 1!=cards[k-i]:
# 「i」が書けなくなる⇔書ける種類が一つ減る
cards[k-i]-=1
# (k-i)=0なら
else:
# 次のiへ
break
# 答え
ans=1
# i=1~N
for i in range(1,N+1):
# 各カードに書ける種類の数を掛ける
ans*=cards[i]
# 余りを取る
ans%=mod
# 答えの出力
print(ans)
ARC124 B
提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
# Bをソート
B.sort()
# 答えの格納(重複除去のためセット)
ans=set()
# i=0~(N-1)
for i in range(N):
# 答えの候補=x
x=A[0]^B[i]
# 計算結果を格納するリスト
C=[]
# i=0~(N-1)
for i in range(N):
# 計算結果を格納
C.append(A[i]^x)
# ソート(Bと一致するか確認のため)
C.sort()
# BとCが一致するなら
if B==C:
# 答え
ans.add(x)
# ソートのためリストへ
ans=list(ans)
# ソート
ans.sort()
# 答えを出力
print(len(ans))
for x in ans:
print(x)
ARC125 A
提出
# 入力の受け取り
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
# 「0」がTにあるかつ「0」がSにない
if 0 in T and 0 not in S:
# 一致させることが不可能
print(-1)
# 終了
exit()
# 「1」がTにあるかつ「1」がSにない
if 1 in T and 1 not in S:
# 一致させることが不可能
print(-1)
# 終了
exit()
# 操作回数
count=0
# 「今先頭に来ている要素」のインデックス番号
# 最初は0
now=0
# j<Mの間
for j in range(M):
# ・「今先頭に来ている要素」=T[j]
# S[now]＝T[i]なら
if S[now]==T[j]:
# 「bへ追加」
count+=1
# 次のjへ
continue
# ・「今先頭に来ている要素」≠T[j]
# i=1~N
for i in range(1,N+1):
# 左にi回シフトしてT[i]と一致したら
if S[(now+i)%N]==T[j]:
# 「左へのシフト」をi回
count+=i
# 「bへ追加」
count+=1
# 「今先頭に来ている要素」のインデックス番号
now=(now+i)%N
# 次のjへ
break
# i回右シフト⇔S[now]から左にi移動してT[i]と一致したら
elif S[(now-i)%N]==T[j]:
# 「右へのシフト」をi回
count+=i
# 「bへ追加」
count+=1
# 「今先頭に来ている要素」のインデックス番号
now=(now-i)%N
# 次のjへ
break
# 答えの出力
print(count)
ARC126 A
提出
# 入力の受け取り
T=int(input())
# T回
for i in range(T):
# 入力の受け取り
N2,N3,N4=map(int,input().split())
# 答え
ans=0
# (1)3*2本,4*1本
# 「10」を作った本数
count=min(N3//2,N4)
# 答えに加算
ans+=count
# 使った本数をマイナス
N3-=count*2
N4-=count
# (2)3*2本,2*2本
count=min(N3//2,N2//2)
ans+=count
N2-=count*2
# (3)2*1本,4*2本
count=min(N2,N4//2)
ans+=count
N2-=count
N4-=count*2
# (4)2*3本,4*1本
count=min(N2//3,N4)
ans+=count
N2-=count*3
N4-=count
# (5)2*5本
count=N2//5
ans+=count
print(ans)
ARC127 A
提出
# Nを文字列で受け取り
N=input()
# Nの桁数
Nd=len(N)
# 整数へ変換
N=int(N)
# 答え
ans=0
# 『(xの桁数)<(Nの桁数)の場合』
# xの桁数：d=1~((Nの桁数)-1)
for d in range(1,Nd):
# 先頭に並ぶ1の個数：num=1~(xの桁数)
for num in range(1,d+1):
# ・(先頭に並ぶ1の個数)<(xの桁数)の場合(=11○△△)
if num<d:
# 場合の数：9*10^((xの桁数)-(先頭に並ぶ1の個数)-1)
count=9*10**(d-num-1)
# ・(先頭に並ぶ1の個数)=(xの桁数)の場合(=11111)
else:
# 場合の数：1
count=1
# 合計：(場合の数)*(先頭に並ぶ1の個数)
ans+=num*count
# 『(xの桁数)=(Nの桁数)の場合』
# 先頭に並ぶ1の個数：num=1~(Nの桁数)
for num in range(1,Nd+1):
# (先頭に並ぶ1の個数)=numのうち最小の数≤N
# ⇔(「1」がnum個と、後ろに「0」を並べた数)≤N
if int("1"*num+"0"*(Nd-num))<=N:
# 場合の数
count=0
# (1)(先頭に並ぶ1の個数)=(Nの桁数)
# 例：11111
if num==Nd:
# (「1」がnum個並んだ数)≤N
if int("1"*num)<=N:
# 場合の数=1
count=1
# (2)(先頭に並ぶ1の個数)=((Nの桁数)-1)
# 例：1111○
elif num==Nd-1:
# maru：○の値
for maru in (0,2,3,4,5,6,7,8,9):
# (「1」がnum個と、「maru」をつけた数)≤N
if int("1"*num+str(maru))<=N:
# 場合の数プラス1
count+=1
# (3)(先頭に並ぶ1の個数)≤((Nの桁数)-2)
# 例：1○△△△,11○△△,111○△
else:
# maru：○の値
for maru in (0,2,3,4,5,6,7,8,9):
# (「1」がnum個、「maru」、残りが「9」)≤N
if int("1"*num+str(maru)+"9"*(Nd-num-1))<=N:
# 場合の数：それぞれの△には0~9(10通り)の任意の数が入る
count+=10**(Nd-num-1)
# (「1」がnum個、「maru」、残りが「0」)≤N
elif int("1"*num+str(maru)+"0"*(Nd-num-1))<=N:
# Nを文字列へ
N=str(N)
# Nの下(△の個数)桁+1
count+=int(N[num+1:])+1
# Nを整数へ戻す
N=int(N)
# 合計：(場合の数)*(先頭に並ぶ1の個数)
ans+=num*count
# 答えの出力
print(ans)
ARC128 A
提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 行動
v=[0]*N
# i=0~(N-2)
for i in range(N-1):
# 金安銀高になるなら
if A[i+1]<A[i]:
# 今日の夜：金を売って銀を買う
# その日の売買が1回なら
if v[i]==0:
# 「1」を記録
v[i]=1
# その日の売買が2回なら
else:
# 「0」を記録
v[i]=0
# 明日の朝：銀を売って金を買う
v[i+1]=1
print(*v)
ARC128 B
提出
# 入力の受け取り
T=int(input())
# T回
for i in range(T):
# 入力の受け取り
R,G,B=map(int,input().split())
# R≤G≤Bとなるように数字を入れ替える
# リストへ格納
tmp=[R,G,B]
# 小さい順に並び替え
tmp.sort()
# 格納し直し
R=tmp[0]
G=tmp[1]
B=tmp[2]
# 答え 初期値はバカでかい値にしておく
ans=10**15
# 「RとG」
# 差が3の倍数なら
if (G-R)%3==0:
# 操作回数=(G-R)/3
tmp_ans=(G-R)//3
# R,Gの値は(G-操作回数)
# R=G=0にする
tmp_ans+=G-tmp_ans
# 答えを更新
ans=min(ans,tmp_ans)
# 「GとB」
# 差が3の倍数なら
if (B-G)%3==0:
# 操作回数=(B-G)/3
tmp_ans=(B-G)//3
# G,Bの値は(B-操作回数)
# G=B=0にする
tmp_ans+=B-tmp_ans
ans=min(ans,tmp_ans)
# 「BとR」
# 差が3の倍数なら
if (B-R)%3==0:
# 操作回数=(B-R)/3
tmp_ans=(B-R)//3
# R,Bの値は(B-操作回数)
# R=B=0にする
tmp_ans+=B-tmp_ans
# 答えを更新
ans=min(ans,tmp_ans)
# もし答えが更新されていなければ
if ans==10**15:
# 「-1」を出力
print(-1)
# そうでなければ
else:
# 答えを出力
print(ans)
別解
# 操作回数を計算する関数
# 引数：操作する色の組 → 返り値：操作回数(同じ数に出来ないなら10^15)
def count(X,Y):
# |X-Y|=差が3の倍数なら
if abs(X-Y)%3==0:
# 操作回数
result=abs(X-Y)//3
result+=max(X,Y)-result
# 操作回数を返す
return result
# そうでなければ(差が3の倍数でない)
else:
# 10^15を返す
return 10**15
# 入力の受け取り
T=int(input())
# T回
for i in range(T):
# 入力の受け取り
R,G,B=map(int,input().split())
# 答え初期値はバカでかい値にしておく
ans=10**15
# それぞれの組み合わせについて操作回数を計算
ans=min(ans,count(R,G))
ans=min(ans,count(G,B))
ans=min(ans,count(B,R))
# もし答えが更新されていなければ
if ans==10**15:
# 「-1」を出力
print(-1)
# そうでなければ
else:
# 答えを出力
print(ans)
クラス解説：UnionFind
全体
# UnionFind
class UnionFind:
# UnionFind(N)：要素数Nで初期化。
# 引数：N(要素数) → 返り値：なし
def __init__(self,N):
# 要素数
self.N=N
# 根の番号 と 木の要素数
# マイナスの場合:グループの要素数(自身が根)
# プラスの場合:根の番号
self.parent_size=[-1]*N
# leader(a)：aの根を返す
# 引数：a → 返り値：aの根
def leader(self,a):
# aが根ならa自身を返す
if self.parent_size[a]<0: return a
# aが根でないなら根に向かって木をたどる＋根の更新
self.parent_size[a]=self.leader(self.parent_size[a])
# 根を返す
return self.parent_size[a]
# merge(a,b)：aとbを連結
# 引数：a,b → 返り値：なし
def merge(self,a,b):
# a,bの根をx,yへ
x,y=self.leader(a),self.leader(b)
# 根が同じなら終了
if x == y: return
# 木の要素数を比較 小さい方を大きい方につなげるため
# x<yならばx,yを入れ替える(xを大きい方にしたい)
if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
# 要素数の更新：小さい方の要素数を大きい方の要素数に足す
self.parent_size[x] += self.parent_size[y]
# 要素数が小さい方の根を大きい方の根につなげる
self.parent_size[y]=x
# same(a,b)：aとbの根が同じか確認
# 引数：a,b → 返り値：True(根が同じ) False(根が違う)
def same(self,a,b):
# 根を比較し、同じならTrueを返す
return self.leader(a) == self.leader(b)
# size(a)：aが属する木の要素数
# 引数：a → 返り値：aが属する木の要素数
def size(self,a):
# 根の絶対値(=要素数)を返す
return abs(self.parent_size[self.leader(a)])
# groups()：それぞれの木の内容を二次元配列として返す
# 引数：なし → 返り値：木の内容
def groups(self):
# グループの格納リストを作る
result=[[] for _ in range(self.N)]
# リストの生成
for i in range(self.N):
result[self.leader(i)].append(i)
# 空の要素を消す
return [r for r in result if r!=[]]
クラス解説：FenwickTree
全体
# FenwickTree
class FenwickTree:
# 「FenwickTree(N)：要素数Nで初期化」
# 引数：N → 返り値：なし
def __init__(self,N):
self.N=N
# F：長さNのリスト
self.F=[0]*N
# 「add(i,x)：i番目の要素にxを加算」
# 引数：i,x → 返り値：なし
def add(self,i,x):
# 1インデックスにするため1を加算
i+=1
# i≤Nの間
while i<=self.N:
# xを加算
# iはプラス1されているのでF[i-1]に加算
self.F[i-1]+=x
# 次のi
i+=i&-i
# 「sum_r(r)：区間[0,r)の区間和を計算」
# 引数：r → 返り値：区間[0,r)の区間和
def sum_r(self,r):
# 合計
s=0
# 0<rの間
while 0<r:
# sに加算
s+=self.F[r-1]
# 次のr
r-=r&-r
# 合計を返す
return s
# 「sum(l,r)：区間[l,r]の区間和を計算」
# 引数：l,r → 返り値：区間[l,r]の区間和
def sum(self,l,r):
# 「区間[l,r]の区間和」=「区間[0,r+1)の区間和」-「区間[0,l)の区間和」
return self.sum_r(r+1)-self.sum_r(l)
# 「select(i)：i番目の要素を出力」
# 引数：i → 返り値：i番目の要素
def select(self,i):
# 区間[i,i]の区間和
return self.sum(i,i)