長さの数列に対して、以下のことを行える。 前処理 昇順ソートする 以上の/以下の/より大きい/より小さい要素の個数 以上の/より大きい要素のうち最小のindex 以下の/より小さい要素のうち最大のindex l.sort() from bisect import bisect_left,bisect_right…

トポロジカルソート 有向グラフの閉路の検出とトポロジカルソート 閉路あり→ -1 閉路なし→ list（任意の有向辺に対し） 計算量 ( :頂点数, :辺の数) def topo_sort(g,n): order=[] indeg=[0]*n for v in range(n): for v1 in g[v]: indeg[v1]+=1 st=[v for v…

桁DP以下の数のうち条件を満たすものを答えよというような問題で使える。計算量 （：状態数、：桁に置ける数字の種類）ソースコード 以下に必ずなるかを表す添字が肝となるが、遷移を書くのによく手間取る。のことを考えなくても書けるソースコードを示す。 …

エラトステネスの篩以下の数に対して、以下のことができる。 前処理 素数判定 素因数分解 約数の個数 約数の総和 約数列挙 ソースコード _n=10**5 #最大値 sieve=list(range(_n+1)) sieve[0]=sieve[1]=-1 for i in range(2,int(_n**0.5)+1): if sieve[i]==i:…

二次元IMOS法の二次元配列に対して、以下のことができる。 区間作用(構築前のみ) 構築 一点取得(構築後のみ) ソースコード class IMOS2: def __init__(self,h,w): self.h,self.w=h+1,w+1 self.l=[0]*(self.h*self.w) def add(self,i,j,i_,j_,x): #矩形[(i,j)…

IMOS法長さの数列に対して、以下のことができる。 区間作用(構築前のみ) 構築 一点取得(構築後のみ) ソースコード class IMOS: def __init__(self,n): self.n=n+1 self.l=[0]*self.n def add(self,i,j,x): #区間[i,j)に+xを区間作用 self.l[i]+=x self.l[j]-…

二次元累積和(群の区間取得)の二次元配列、集合二項演算子(は群)に対して、以下のことができる。 前処理 区間取得 群は結合律・単位律・逆元律を満たす。 ソースコード(二項演算子が加算の場合) class Acc2: def __init__(self,l,f,unit,inv): self.h,self.w…

累積min(モノイドの端からの区間取得)長さの数列、集合、二項演算子(はモノイド)に対して、以下のことができる。 前処理 端からの区間取得 モノイドは結合律・単位律を満たす。 ソースコード(二項演算子がminの場合) from itertools import accumulate class…

累積和(群の区間取得)長さの数列、集合、二項演算子(は群)に対して、以下のことができる。 前処理 区間取得 群は結合律・単位律・逆元律を満たす。 ソースコード(二項演算子が加算の場合) from itertools import accumulate class Acc: def __init__(self,l,…