タコヤキオイシクナールはセグメントツリーの応用の典型例として有名です。
対象読者は、セグメントツリー上にMaxやSumがどうして乗るかを(なんとなく)理解しており、タコヤキオイシクナールをどのように乗せればよいのか？と悩んでいる人を対象とします。
概要
簡単のために以下のように言い換えます。
- n 個の箱があり、それぞれの箱$a_i (0 \leq i < n)$にはa,b の変数が書かれている。すべての箱は1,0のパラメータを持つ。
- 各箱はxという値が入力されると $ ax + b $を出力する。
- 今、1という数字を$a_0$にいれる。$a_i$に入力された値の出力は$a_{i+1}$に渡され
- すべての箱を通過した時の値は何か？
例
2つの箱がありパラメータが$2,2$と$3,3$だったとします。
1つ目の箱の入力は1のため、$1 * 2 + 2$で5が出力されます。
2つ目の箱の入力は5のため、$5 * 2 + 3$で18が出力されます。
箱の合成
隣接する箱を合成することが可能です。1つ目の箱のパラメータをa,bとし、2つめの箱のパラメータをc,dとします。
最初に値xが箱1に入るとき、与えられた条件より、箱2では$((ax + b)c + d)$を出力します。これを式変形します。
$ ((ax + b)c + d) = (ac)x + (bc + d)$です。つまり1つ目と2つ目の箱を通過するとは、パラメータが$ac, (bc + d)$の箱を通過すると同じです。これを合成と呼ぶことにします。
箱において$a,b$と$1,0$のパラメータは単位元となる特殊な箱です。特殊で合成した箱は$a,b$のままです。上記の式に当てはめると$a1x + (b*1 + 0) = ax + b$で$a,b$の箱と等価になりました。
セグメントツリーへの実装
セグメントツリーのノードには1値の数値ではなくて、$a,b$の2値を持たせます。
$1,0$のパラメータはタコヤキオイシクナールにおいて単位元としての役割を持ちます。他の箱の演算結果に影響を与えません。セグメントツリーのノードをすべて$1,0$で初期化します。
セグメントツリーでは配下の2ノードごとの演算を定義しますが、ここでは、合成と同じ、$((ax + b)c + d) = (ac)x + (bc + d)$を乗せます。この問題では1点更新のみで区間更新は考慮する必要はありません。
クエリを考えます。この問題においては全区間のクエリのみを考えればよく、ノード0のみの情報を用いればよいです。ノード0の$a,b$は全区間の箱を通した結果と等しくなるためです。
満点解法のポイント:座標圧縮
上記の解法では満点を取ることはできません。これは、$0 < N \leq 10^{12}$とNが大きく、セグメントツリーに乗せることが空間量的にできないからです。Mが$10^6$以下と小さいことに注目します。座標圧縮しましょう。
$10$と$10^{10}$の２つの箱だけを値$a,bとc,d$に変えたとするのと、$1$と$2$の箱を値$a,bとc,d$に変えたものは結果に影響を与えません。クエリを先読みして座標圧縮を行い、大でM個の箱しか存在しないと考えます。
class segmentTree():
initValue = [1, 0]
dat = []
lenTreeLeaf = -1
depthTreeList = 0
lenOriginalList = -1
func = None
N = -1
def load(self, l):
self.N = len(l)
self.lenOriginalList = self.N # original nodes
self.depthTreeList = (self.N - 1).bit_length() # Level of Tree
self.lenTreeLeaf = 2 ** self.depthTreeList # leaf of node, len 5 -> 2^3 = 8
self.dat = [self.initValue] * (self.lenTreeLeaf * 2)
# Load Function
for i in range(len(l)):
self.dat[self.lenTreeLeaf - 1 + i] = l[i]
self.build()
def build(self):
for i in range(self.lenTreeLeaf - 2, -1, -1):
self.dat[i] = self.func(self.dat[2 * i + 1], self.dat[2 * i + 2])
def setValue(self, ind, value):
nodeId = (self.lenTreeLeaf - 1) + ind
self.dat[nodeId] = value
while nodeId != 0:
nodeId = (nodeId - 1) // 2
self.dat[nodeId] = self.func(self.dat[nodeId * 2 + 1], self.dat[nodeId * 2 + 2])
def res(self):
return self.dat[0][0] + self.dat[0][1]
class segmentTreeTako(segmentTree):
def __init__(self):
self.func = lambda x, y: [x[0] * y[0], x[1] * y[0] + y[1]]
self.initValue = [1, 0]
n, m = map(int, input().split())
aa = 1
bb = 1
dat = []
k = dict()
for i in range(m):
p, a, b = map(float, input().split())
p = int(p)
k[p] = True
dat.append([p, a, b])
zatu = list(k.keys())
zatu.sort()
zatu = list(enumerate(zatu))
trans = dict()
for i in range(len(zatu)):
trans[zatu[i][1]] = zatu[i][0]
st = segmentTreeTako()
l = [[1, 0]] * (len(zatu) + 10)
st.load(l)
for i in range(m):
p, a, b = dat[i]
p = trans[p]
st.setValue(p, [a, b])
res = st.res()
aa = max(aa, res)
bb = min(bb, res)
print(bb)
print(aa)