[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.


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?


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]

    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 = 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)

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)


Recommended Posts

How to put Takoyaki Oishikunaru on the segment tree
Think about how to program Python on the iPad
How to visualize the decision tree model of scikit-learn
How to enjoy Python on Android !! Programming on the go !!
How to use the generator
How to register on pypi
How to use the decorator
How to increase the axis
How to start the program
[Hyperledger Iroha] Notes on how to use the Python SDK
How to deploy the easiest python textbook pybot on Heroku
Notes on how to use marshmallow in the schema library
How to print characters to the console before booting on ARM
How to calculate the autocorrelation coefficient
How to use the zip function
How to use the optparse module
How to put a symbolic link
A note on how to check the connection to the license server port
How to install mysql-connector-python on mac
How to use Dataiku on Windows
How easy is it to synthesize a drug on the market?
Notes on how to use pywinauto
How to install graph-tool on macOS
How to install VMware-Tools on Linux
How to install pycrypto on Windows
How to read the SNLI dataset
How to deploy django-compressor on Windows
How to get the Python version
Notes on how to use featuretools
How to install OpenCV on Mac
How to run matplotlib on heroku
How to use python put in pyenv on macOS with PyCall
How to install PyPy on CentOS
How to use homebrew on Debian
[Python] How to import the library
Misunderstanding on how to connect cnn
How to install TensorFlow on CentOS 7
How to use Jupyter on the front end of supercomputer ITO
How to overwrite the output to the console
How to update the python version of Cloud Shell on GCP
Try to implement and understand the segment tree step by step (python)
Notes on how to use doctest
How to install Maven on CentOS
How to use the ConfigParser module
Notes on how to write requirements.txt
How to install Go on Ubuntu
How to install music 21 on windows
Put Cabocha 0.68 on Windows and try to analyze the dependency with Python
How to easily switch the virtual environment created by Conda on Jupyter
How to put a line number at the beginning of a CSV file
Matching karaoke keys ~ I tried to put it on Laravel ~ <on the way>
[C language] How to use the crypt function on Linux [Password hashing]
TLE seemed to be scary depending on how the input was received
How to make only one data register on the Django admin screen
How to display the progress bar (tqdm)
How to use the Spark ML pipeline
How to install aws-session-manager-plugin on Manajro Linux
How to read pydoc on python interpreter
How to install drobertadams / toggl-cli on Mac
How to check the version of Django
[Kivy] How to install Kivy on Windows [Python]