<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 SortedSet
import bisect

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

        # Two soluton SortedList (Multiset/Treeset) and REVERSE UNION FIND **

        n = len(nums)
        s = SortedSet([0])  # Use SortedSet to maintain sorted order with unique elements
        in_segments = SortedSet([(0, n - 1)])
        
        # Compute prefix sums
        pre = [0] * n
        pre[0] = nums[0]
        for i in range(1, n):
            pre[i] = pre[i - 1] + nums[i]
        
        # Insert the sum of the whole array initially
        s.add(pre[n - 1])
        
        ans = []
        
        for p in removeQueries:
            # Find the segment containing index p
            idx = bisect.bisect_right(in_segments, (p, float('inf'))) - 1
            it = in_segments[idx]
            
            # Calculate segment sums
            L = (pre[p - 1] if p > 0 else 0) - (pre[it[0] - 1] if it[0] > 0 else 0)
            R = pre[it[1]] - pre[p]
            T = pre[it[1]] - (pre[it[0] - 1] if it[0] > 0 else 0)
            
            # Remove the total segment sum
            s.remove(T)
            
            # Update segments and their sums
            if it[0] <= p - 1:
                in_segments.add((it[0], p - 1))
                s.add(L)
            
            if it[1] >= p + 1:
                in_segments.add((p + 1, it[1]))
                s.add(R)
            
            in_segments.remove(it)
            
            # Record the maximum sum
            ans.append(s[-1])
        
        return ans
"""                    [ [ REVERSE DSU ] ]                           """
# ******************** [ [ REVERSE DSU ] ] Solution ********************
"""                    [ [ REVERSE DSU ] ]                           """

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.sum = {}
        self.maxSumSegment = 0
        
    def addAndMergeAdjSegment(self, u, value):
        self.parent[u] = u
        self.sum[u] = value
        self.maxSumSegment = max(self.maxSumSegment, value)
        if u-1 in self.parent:
            self.union(u, u-1)
        if u+1 in self.parent:
            self.union(u, u+1)
        
    def find(self, u):
        if u != self.parent[u]:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]
    
    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv: return
        self.sum[pu] += self.sum[pv]
        self.parent[pv] = pu
        self.maxSumSegment = max(self.maxSumSegment, self.sum[pu])

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        uf = UnionFind()
        
        ans = [0] * n
        for i in range(n-1, -1, -1):
            ans[i] = uf.maxSumSegment
            q = removeQueries[i]
            uf.addAndMergeAdjSegment(q, nums[q])
        return ans

# This make sense understand this  ( nums and removeQueries, both of length n. )
# so in reverse union find it works
# The Below is More clear code if you dont understand the above 

# class DSU:
#     def __init__(self, n, value):
#         self.n = n
#         self.lead = list(range(n))
#         self.size = [1] * n
#         self.sum = value[:]
#         self.max_value = max(value)
        
#     def leader(self, x):
#         if x == self.lead[x]:
#             return x
#         self.lead[x] = self.leader(self.lead[x])
#         return self.lead[x]
    
#     def merge(self, x, y):
#         x = self.leader(x)
#         y = self.leader(y)
#         if x == y:
#             return
#         if self.size[x] > self.size[y]:
#             x, y = y, x
#         self.size[y] += self.size[x]
#         self.sum[y] += self.sum[x]
#         self.lead[x] = y
#         self.max_value = max(self.max_value, self.sum[y])

# class Solution:
#     def maximumSegmentSum(self, nums, removeQueries):
#         n = len(nums)
#         q = len(removeQueries)
        
#         with_removed = nums[:]
#         for i in removeQueries:
#             with_removed[i] = 0
        
#         prefix = [0] * n
#         prefix[0] = nums[0]
#         for j in range(1, n):
#             prefix[j] = prefix[j-1] + nums[j]
        
#         dsu = DSU(n, with_removed)
        
#         j = 0
#         while j < n:
#             if with_removed[j] == 0:
#                 j += 1
#                 continue
            
#             start = j
#             while j < n and with_removed[j] != 0:
#                 dsu.merge(start, j)
#                 j += 1
        
#         result = [0] * q
#         for j in range(q-1, -1, -1):
#             result[j] = dsu.max_value
            
#             ind = removeQueries[j]
#             with_removed[ind] = nums[ind]
            
#             dsu.sum[ind] = nums[ind]
#             dsu.max_value = max(dsu.max_value, dsu.sum[ind])
            
#             if ind > 0 and with_removed[ind-1] != 0:
#                 dsu.merge(ind, ind-1)
#             if ind < n-1 and with_removed[ind+1] != 0:
#                 dsu.merge(ind, ind+1)
        
#         return result



54800