[PYTHON] How to put Takoyaki Oishikunaru on the segment tree

Takoyaki Oishikunaru is a well-known example of segment tree applications. This time we will solve this problem. The target audience understands the implementation of Max and Sum in the segment tree, and how to put Takoyaki Oishikunaru on it? It is intended for those who are worried.

Overview

First, think without considering the perfect score method.

--There are n boxes, and each box $ a_i (0 \ leq i <n) $ contains variables a and b. All boxes have a parameter of 1,0. --Each box outputs $ ax + b $ when the value x is entered. --Now, put the number 1 in $ a_0 $. The output of the value entered in $ a_i $ is passed to $ a_ {i + 1} $ ――What is the value when passing through all the boxes?

Example

Suppose you have two boxes with parameters of $ 2,2 $ and $ 3,3 $ respectively. Since the input of the first box is 1, $ 1 * 2 + 2 $ will output 5. The input for the second box is 5, so $ 5 * 2 + 3 $ will output 18.

Box composition

Adjacent boxes can be combined. Now let the parameters of the first box be a and b and the parameters of the second box be c and d. When the value x first enters box 1, box 2 outputs $ ((ax + b) c + d) $ under the given conditions. This is transformed into an equation. $ ((ax + b) c + d) = (ac) x + (bc + d) $. This is the same as a box with parameters $ ac, (bc + d) $. We will call this synthesis.

If the adjacent boxes have parameters of $ a, b $ and $ 1,0 $, the combined box remains $ a, b $. As shown in the above formula, $ a * 1 * x + (b * 1 + 0) = ax + b $, which is equivalent to the box of $ a, b $.

Implementation in segment tree

The nodes in the segment tree should have two values, $ a and b $, instead of a one-value number. Here, the $ 1,0 $ parameter serves as the identity element in Takoyaki Oishikunaru. It does not affect the calculation results of other boxes. First, initialize all the nodes in the segment tree for $ 1,0 $.

In the segment tree, the operation for each of the two nodes under it is defined, but here, the same as for synthesis, $ ((ax + b) c + d) = (ac) x + (bc + d) $ is added. In this problem, only one point update is required, and there is no need to consider interval update or interval addition.

Next, consider a query. It is troublesome to write a query for the segment tree in the sky, but in this problem, you only need to consider the query for the entire section, and use the information for node 0 only. This is because $ a and b $ of node 0 are equal to the result of passing through the boxes of all intervals.

Points of perfect score solution

You cannot get a perfect score with the above solution. This is because $ 0 <N \ leq 10 ^ {12} $ and N are large and cannot be placed in the segment tree spatially. However, note that M is as small as $ 10 ^ 6 $ or less. For example, suppose you change only two boxes of $ 10 $ and $ 10 ^ 10 $ to the values ​​$ a, b and c, d $, and you change the boxes of $ 1 $ and $ 2 $ to the values ​​$ a, b and c, d $. What you change to does not affect the result. Therefore, it can be calculated by performing coordinate compression and assuming that there are at most M boxes at most. (Even if M = $ 10 ^ 6 $, it may not be all operations for the same box, so it may not be necessary to prepare M boxes, but assuming that there is M has no effect. .)

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)