<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums</code> and <code>removeQueries</code>, both of length <code>n</code>. For the <code>i<sup>th</sup></code> query, the element in <code>nums</code> at the index <code>removeQueries[i]</code> is removed, splitting <code>nums</code> into different segments.</p>

<p>A <strong>segment</strong> is a contiguous sequence of <strong>positive</strong> integers in <code>nums</code>. A <strong>segment sum</strong> is the sum of every element in a segment.</p>

<p>Return<em> an integer array </em><code>answer</code><em>, of length </em><code>n</code><em>, where </em><code>answer[i]</code><em> is the <strong>maximum</strong> segment sum after applying the </em><code>i<sup>th</sup></code> <em>removal.</em></p>

<p><strong>Note:</strong> The same index will <strong>not</strong> be removed more than once.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
<strong>Output:</strong> [14,7,2,2,0]
<strong>Explanation:</strong> Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 0th element, nums becomes [0,2,5,6,1] and the maximum segment sum is 14 for segment [2,5,6,1].
Query 2: Remove the 3rd element, nums becomes [0,2,5,0,1] and the maximum segment sum is 7 for segment [2,5].
Query 3: Remove the 2nd element, nums becomes [0,2,0,0,1] and the maximum segment sum is 2 for segment [2]. 
Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment [2]. 
Query 5: Remove the 1st element, nums becomes [0,0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [14,7,2,2,0].</pre>

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

<pre>
<strong>Input:</strong> nums = [3,2,11,1], removeQueries = [3,2,1,0]
<strong>Output:</strong> [16,5,3,0]
<strong>Explanation:</strong> Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 3rd element, nums becomes [3,2,11,0] and the maximum segment sum is 16 for segment [3,2,11].
Query 2: Remove the 2nd element, nums becomes [3,2,0,0] and the maximum segment sum is 5 for segment [3,2].
Query 3: Remove the 1st element, nums becomes [3,0,0,0] and the maximum segment sum is 3 for segment [3].
Query 4: Remove the 0th element, nums becomes [0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [16,5,3,0].
</pre>

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

<ul>
	<li><code>n == nums.length == removeQueries.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= removeQueries[i] &lt; n</code></li>
	<li>All the values of <code>removeQueries</code> are <strong>unique</strong>.</li>
</ul>

from sortedcontainers import SortedList
import heapq

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:

        def findPoint(p, start, end):
            if start > end:
                return None
            if start == end:
                if sorted_list[start][0] <= p and sorted_list[start][1] >= p:
                    return sorted_list[start]
                return None
            mid = (start + end)//2
            if sorted_list[mid][0] <= p and sorted_list[mid][1] >= p:
                return sorted_list[mid]
            if sorted_list[mid][0] > p:
                return findPoint(p, start, mid-1)
            return findPoint(p, mid+1, end)

        def getSum(tupel):
            return -(sumArr[tupel[1]] - sumArr[tupel[0]-1] if tupel[0] > 0 else sumArr[tupel[1]])

        sumArr = []
        for num in nums:
            if not sumArr:
                sumArr = [num]
                continue
            sumArr.append(sumArr[-1] + num)

        sorted_list = SortedList()
        sorted_list.add((0, len(nums)-1))
        ans = []
        heap = []
        to_remove = {}

        for i in range(len(removeQueries)):
            curr = findPoint(removeQueries[i], 0, len(sorted_list)-1)
            sorted_list.discard(curr)
            val = sumArr[curr[1]] - sumArr[curr[0]-1] if curr[0] > 0 else sumArr[curr[1]]
            if val in to_remove:
                to_remove[val] += 1
            else:
                to_remove[val] = 1
            if curr[0] == removeQueries[i]:
                if curr[1] > curr[0]:
                    sorted_list.add((curr[0]+1, curr[1]))
                    heapq.heappush(heap, getSum((curr[0] + 1, curr[1])))
            elif curr[1] == removeQueries[i]:
                if curr[1] > curr[0]:
                    sorted_list.add((curr[0], curr[1]-1))
                    heapq.heappush(heap, getSum((curr[0], curr[1]-1)))
            else:
                sorted_list.add((curr[0], removeQueries[i] - 1))
                sorted_list.add((removeQueries[i] + 1, curr[1]))
                heapq.heappush(heap, getSum((curr[0], removeQueries[i] - 1)))
                heapq.heappush(heap, getSum((removeQueries[i] + 1, curr[1])))
            
            flag = True
            while heap:
                popped = -heap[0]
                if popped in to_remove:
                    heapq.heappop(heap)
                    if to_remove[popped] == 1:
                        del to_remove[popped]
                        continue
                    to_remove[popped] -= 1
                    continue
                ans.append(popped)
                flag = False
                break
            
            if flag:
                ans.append(0)
                    
        return ans

45100