<p>You have <code>n</code> robots. You are given two <strong>0-indexed</strong> integer arrays, <code>chargeTimes</code> and <code>runningCosts</code>, both of length <code>n</code>. The <code>i<sup>th</sup></code> robot costs <code>chargeTimes[i]</code> units to charge and costs <code>runningCosts[i]</code> units to run. You are also given an integer <code>budget</code>.</p>

<p>The <strong>total cost</strong> of running <code>k</code> chosen robots is equal to <code>max(chargeTimes) + k * sum(runningCosts)</code>, where <code>max(chargeTimes)</code> is the largest charge cost among the <code>k</code> robots and <code>sum(runningCosts)</code> is the sum of running costs among the <code>k</code> robots.</p>

<p>Return<em> the <strong>maximum</strong> number of <strong>consecutive</strong> robots you can run such that the total cost <strong>does not</strong> exceed </em><code>budget</code>.</p>

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

<pre>
<strong>Input:</strong> chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
It is possible to run all individual and consecutive pairs of robots within budget.
To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25.
It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.
</pre>

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

<pre>
<strong>Input:</strong> chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
<strong>Output:</strong> 0
<strong>Explanation:</strong> No robot can be run that does not exceed the budget, so we return 0.
</pre>

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

<ul>
	<li><code>chargeTimes.length == runningCosts.length == n</code></li>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= chargeTimes[i], runningCosts[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= budget &lt;= 10<sup>15</sup></code></li>
</ul>

import heapq
from typing import List

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)  # Segment tree array
        self.build(data, 0, 0, self.n - 1)

    def build(self, data, node, start, end):
        if start == end:
            # Leaf node will have a single element
            self.tree[node] = data[start]
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2

            # Recursively build the segment tree
            self.build(data, left_child, start, mid)
            self.build(data, right_child, mid + 1, end)

            # Internal node will have the maximum of the two children
            self.tree[node] = max(self.tree[left_child], self.tree[right_child])

    def range_max_query(self, l, r):
        # Query the maximum value in the range [l, r]
        return self._range_max_query(0, 0, self.n - 1, l, r)

    def _range_max_query(self, node, start, end, l, r):
        if r < start or l > end:
            # If the range is outside the bounds of this segment
            return float('-inf')
        if l <= start and end <= r:
            # If the segment is completely within the range
            return self.tree[node]

        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2

        # Query the left and right children
        left_max = self._range_max_query(left_child, start, mid, l, r)
        right_max = self._range_max_query(right_child, mid + 1, end, l, r)

        # Return the maximum of both
        return max(left_max, right_max)

    def update(self, idx, value):
        # Update the segment tree when the array value at idx changes
        self._update(0, 0, self.n - 1, idx, value)

    def _update(self, node, start, end, idx, value):
        if start == end:
            # Leaf node
            self.tree[node] = value
        else:
            mid = (start + end) // 2
            left_child = 2 * node + 1
            right_child = 2 * node + 2

            if start <= idx <= mid:
                # Update the left child
                self._update(left_child, start, mid, idx, value)
            else:
                # Update the right child
                self._update(right_child, mid + 1, end, idx, value)

            # Update the internal node with the maximum of its children
            self.tree[node] = max(self.tree[left_child], self.tree[right_child])

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        n = len(chargeTimes)
        i = 0
        j = 0
        maxK = 0
        runningSum = 0
        segTree = SegmentTree(chargeTimes)
        while j < n:
            maxChargeTime = segTree.range_max_query(i, j)
            runningSum += runningCosts[j]
            k = j - i + 1
            cost = maxChargeTime + runningSum * k
            print(j, k, cost, maxChargeTime)

            if cost <= budget:
                maxK = max(maxK, k)
                print("Updates", i, j)
            else:
                runningSum -= runningCosts[i]
                i += 1
            j += 1

        return maxK

26200