''' mbinary
#########################################################################
# File : winnerTree.py
# Author: mbinary
# Mail: zhuheqin1@gmail.com
# Blog: https://mbinary.xyz
# Github: https://github.com/mbinary
# Created Time: 2018-05-19  23:06
# Description:
#########################################################################
'''


class winnerTree:
    '''if i<lowExt    p = (i+offset)//2
       else           p = (i+n-1-lowExt)//2
       offset is a num 2^k-1 just bigger than n
        p is the index of tree
        i is the index of players
        lowExt is the double node num of the lowest layer of the tree
    '''

    def __init__(self, players, reverse=False):
        self.n = len(players)
        self.tree = [0]*self.n
        players.insert(0, 0)
        self.players = players
        self.reverse = reverse
        self.getNum()
        self.initTree(1)

    def getNum(self):
        i = 1
        while 2*i < self.n:
            i = i*2
        if 2*i == self. n:
            self.lowExt = 0
            self.s = 2*i-1
        else:
            self.lowExt = (self.n-i)*2
            self.s = i-1
        self.offset = 2*i-1

    def treeToArray(self, p):
        return 2*p-self.offset if p > self.s else 2*p+self.lowExt-self.n+1

    def arrayToTree(self, i):
        return (i+self.offset)//2 if i <= self.lowExt else (i-self.lowExt + self.n-1)//2

    def win(self, a, b):
        return a < b if self.reverse else a > b

    def initTree(self, p):
        if p >= self.n:
            delta = p % 2  # !!! good job  notice delta mark the lchild or rchlid
            return self.players[self.treeToArray(p//2)+delta]
        l = self.initTree(2*p)
        r = self.initTree(2*p+1)
        self.tree[p] = l if self.win(l, r) else r
        return self.tree[p]

    def winner(self):
        idx = 1
        while 2*idx < self.n:
            idx = 2*idx if self.tree[2*idx] == self.tree[idx] else idx*2+1
        num = self.treeToArray(idx)
        num = num+1 if self.players[num] != self.tree[1] else num
        return self.tree[1], num

    def getOppo(self, i, x, p):
        oppo = None
        if 2*p < self.n:
            oppo = self.tree[2*p]
        elif i <= self.lowExt:
            oppo = self.players[i-1+i % 2*2]
        else:
            lpl = self.players[2*p+self.lowExt-self.n+1]
            oppo = lpl if lpl != x else self.players[2*p+self.lowExt-self.n+2]
        return oppo

    def update(self, i, x):
        ''' i is 1-indexed  which is the num of player
            and x is the new val of the player '''
        self.players[i] = x
        p = self.arrayToTree(i)
        oppo = self.getOppo(i, x, p)
        self.tree[p] = x if self.win(x, oppo) else oppo
        p = p//2
        while p:
            l = self.tree[p*2]
            r = None
            if 2*p+1 < self.n:
                r = self.tree[p*2+1]  # notice this !!!
            else:
                r = self.players[2*p+self.lowExt-self.n+1]
            self.tree[p] = l if self.win(l, r) else r
            p = p//2


if __name__ == '__main__':
    s = [4, 1, 6, 7, 9, 5234, 0, 2, 7, 4, 123]
    t = winnerTree(s)
    print(t.players, t.tree)
    for i in s:
        val, idx = t.winner()
        print(val, idx)
        t.update(idx, -1)


'''
[0, 4, 1, 6, 7, 9, 5234, 0, 2, 7, 4, 123] [0, 5234, 5234, 123, 7, 5234, 7, 123, 4, 7, 5234]
5234 6
123 11
9 5
7 4
7 9
6 3
4 1
4 10
2 8
1 2
'''