<p>You are given a <strong>0-indexed</strong> string <code>s</code>. You are also given a <strong>0-indexed</strong> string <code>queryCharacters</code> of length <code>k</code> and a <strong>0-indexed</strong> array of integer <strong>indices</strong> <code>queryIndices</code> of length <code>k</code>, both of which are used to describe <code>k</code> queries.</p>

<p>The <code>i<sup>th</sup></code> query updates the character in <code>s</code> at index <code>queryIndices[i]</code> to the character <code>queryCharacters[i]</code>.</p>

<p>Return <em>an array</em> <code>lengths</code> <em>of length </em><code>k</code><em> where</em> <code>lengths[i]</code> <em>is the <strong>length</strong> of the <strong>longest substring</strong> of </em><code>s</code><em> consisting of <strong>only one repeating</strong> character <strong>after</strong> the</em> <code>i<sup>th</sup></code> <em>query</em><em> is performed.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babacc&quot;, queryCharacters = &quot;bcb&quot;, queryIndices = [1,3,3]
<strong>Output:</strong> [3,3,4]
<strong>Explanation:</strong> 
- 1<sup>st</sup> query updates s = &quot;<u>b<strong>b</strong>b</u>acc&quot;. The longest substring consisting of one repeating character is &quot;bbb&quot; with length 3.
- 2<sup>nd</sup> query updates s = &quot;bbb<u><strong>c</strong>cc</u>&quot;. 
  The longest substring consisting of one repeating character can be &quot;bbb&quot; or &quot;ccc&quot; with length 3.
- 3<sup>rd</sup> query updates s = &quot;<u>bbb<strong>b</strong></u>cc&quot;. The longest substring consisting of one repeating character is &quot;bbbb&quot; with length 4.
Thus, we return [3,3,4].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abyzz&quot;, queryCharacters = &quot;aa&quot;, queryIndices = [2,1]
<strong>Output:</strong> [2,3]
<strong>Explanation:</strong>
- 1<sup>st</sup> query updates s = &quot;ab<strong>a</strong><u>zz</u>&quot;. The longest substring consisting of one repeating character is &quot;zz&quot; with length 2.
- 2<sup>nd</sup> query updates s = &quot;<u>a<strong>a</strong>a</u>zz&quot;. The longest substring consisting of one repeating character is &quot;aaa&quot; with length 3.
Thus, we return [2,3].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
	<li><code>k == queryCharacters.length == queryIndices.length</code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
	<li><code>queryCharacters</code> consists of lowercase English letters.</li>
	<li><code>0 &lt;= queryIndices[i] &lt; s.length</code></li>
</ul>

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        
        tree = SegmentTree(0, len(s) - 1, s)
        res = []

        #tree.dfs(tree.root)


        s = [v for v in s]

        for idx, char in zip(queryIndices, queryCharacters):
            s[idx] = char
            tree.update(idx, idx, char, tree.root)
            res.append(tree.query(0, len(s) - 1, 0, tree.root)[0])

            # if tree.query(0, len(s) - 1, 0, tree.root)[0] == 3:
            #     print(idx)
            #     print(''.join(s))
            #     print(queryCharacters[idx:])
            #     print(queryIndices[idx:])
            #     break


        return res



class TreeNode():
    def __init__(self, lb, rb):
        self.lb = lb
        self.rb = rb

        self.left = None
        self.right = None

        self.maxlenth = 0
        self.maxchar = ""

        self.frontlenth = 0
        self.frontchar = ""

        self.endlenth = 0
        self.endchar = ""
        
        
class SegmentTree:

    def __init__(self, lb, rb, arr):
        self.root = TreeNode(lb, rb)

        self.arr = arr

        self.pushdown(lb, rb, 0, self.root)

    def dfs(self, node):
        if node is None:
            return

        print(node.__dict__)
        self.dfs(node.left)
        self.dfs(node.right)


    def help(self, lb, rb, val, node, func):

        if node is None:
            return 0, 0, 0, 0, 0, 0

        if lb > node.rb or node.lb > rb:
            if func == self.query:
                return 0, 0, 0, 0, 0, 0
            else:
                return node.maxlenth, node.maxchar, node.frontlenth, node.frontchar, node.endlenth, node.endchar

        if node.left is None:
            lmaxlenth, lmaxchar, lfrontlenth, lfrontchar, lendlenth, lendchar = 0, 0, 0, 0, 0, 0
            lsize = 0
        else:
            lmaxlenth, lmaxchar, lfrontlenth, lfrontchar, lendlenth, lendchar = func(lb, rb, val, node.left)
            lsize = node.left.rb - node.left.lb + 1

        if node.right is None:
            rmaxlenth, rmaxchar, rfrontlenth, rfrontchar, rendlenth, rendchar = 0, 0, 0, 0, 0, 0
            rsize = 0
        else:
            rmaxlenth, rmaxchar, rfrontlenth, rfrontchar, rendlenth, rendchar = func(lb, rb, val, node.right)
            rsize = node.right.rb - node.right.lb + 1

        if lmaxlenth >= rmaxlenth:
            maxlenth = lmaxlenth
            maxchar = lmaxchar
        else:
            maxlenth = rmaxlenth
            maxchar = rmaxchar

        if rfrontchar == lendchar and rfrontlenth + lendlenth > maxlenth:
            maxlenth  = rfrontlenth + lendlenth
            maxchar = rfrontchar

        frontchar = lfrontchar
        if lfrontchar == lendchar == rfrontchar and lfrontlenth == lsize:
            frontlenth = lfrontlenth + rfrontlenth
        else:
            frontlenth = lfrontlenth

        endchar = rendchar
        if lendchar == rfrontchar == rendchar and rfrontlenth == rsize:
            endlenth = rendlenth + lendlenth
        else:
            endlenth = rendlenth

        return maxlenth, maxchar, frontlenth, frontchar, endlenth, endchar


    def pushdown(self, lb, rb, val, node):

        mid = (node.lb + node.rb) // 2

        if node.lb != node.rb:
            if node.left is None:
                node.left = TreeNode(node.lb, mid)
            if node.right is None:
                node.right = TreeNode(mid + 1, node.rb)


        if node.lb == node.rb:

            node.maxlenth = 1
            node.maxchar = self.arr[node.lb]

            node.frontlenth = 1
            node.frontchar = self.arr[node.lb]

            node.endlenth = 1
            node.endchar = self.arr[node.lb]

        else:
            node.maxlenth, node.maxchar, node.frontlenth, node.frontchar, node.endlenth, node.endchar =  self.help(lb, rb, 0, node, self.pushdown)


        return node.maxlenth, node.maxchar, node.frontlenth, node.frontchar, node.endlenth, node.endchar
        

    def update(self, lb, rb, val, node):

        if lb <= node.lb <= node.rb <= rb:
            node.maxlenth, node.maxchar, node.frontlenth, node.frontchar, node.endlenth, node.endchar =  1, val, 1, val, 1, val
        else:
            node.maxlenth, node.maxchar, node.frontlenth, node.frontchar, node.endlenth, node.endchar =  self.help(lb, rb, val, node, self.update)

        return node.maxlenth, node.maxchar, node.frontlenth, node.frontchar, node.endlenth, node.endchar


    def query(self, lb, rb, val, node):
        
        if lb <= node.lb and node.rb <= rb:
            return node.maxlenth, node.maxchar, node.frontlenth, node.frontchar, node.endlenth, node.endchar

        return self.help(lb, rb, 0, node, self.query)
6307