(Python)タコヤキオイシクナールをセグメントツリーへの乗せる

タコヤキオイシクナールはセグメントツリーの応用の典型例として有名です。

対象読者は、セグメントツリー上に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$のままです。上記の式に当てはめると$a*1*x + (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個の箱しか存在しないと考えます。

```Python
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)
```