連続する部分列→累積和を取る 累積和をとって、差を考える 余りの種類は m 個あるけど、数列の長さから高々 n 個に座圧できる。 基本テクの詰め合わせ。 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.std…

一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

これの下位互換。 F - Absolute Minima abc 127 F - Absolute Minima (python) - aacord’s memo import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1…

BIT木。初見で解いているときは BIT木を知らなくて TLE を出し続け、諦めて解説読んでナニコレとなった。 BIT木の使いどころは、BIT木を2本持つことで、小さい方から i 番目の値の探索を log(N) を行える点である。値の追加、探索、削除を log(N) でできるの…

k = 0 から順番に (A[k*2],B[k*2]), (A[k*2+1],B[k*2+1]) を (A[k*2]+B[k*2])*A[k*2+1]+B[k*2+1] と計算していく問題。 セグ木を使うと、(A[k*2]*A[k*2+1], B[k*2]*A[k*2+1]+B[k*2+1]) の結果を (A[k], B[k])に保存できるので、求める答えは sum(A[1]+B[1]) …