<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>

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        '''
        将removeQueries倒序相当于从"空序列"(值为0)一个一个添加元素，返回每次添加后的最大子段和

        每次添加会改变关联关系(是否连成子段)，利用并查集维护

        子段和计算:

        同时在并查集中记录某个位置所在子段的和(通过find到根节点可得每个子段的和)
        每次union时, 被union的段的和累加到根节点上(统一向右侧union)
        是否最大:

        在逐渐还原的过程中, 只需要与上一次的结果作比较

        '''
        n = len(nums)
        pa = list(range(n+1))
        total = [0] * (n+1)
        def find(x):
            if pa[x] != x:
                pa[x] = find(pa[x])
            return pa[x]
        res = [0] * n
        for i in range(n-1, 0, -1):
            x = removeQueries[i]
            to = find(x+1)
            pa[x] = to
            total[to] += total[x] + nums[x]
            res[i-1] = max(res[i], total[to])
        return res
        

        # n = len(nums)
        # ans = [0]
        # last = 0
        # d = {}  # {num: [len, sum]}
        # for rmIdx in reversed(removeQueries[1:]):
        #     if rmIdx not in d:
        #         # 找点rmIdx附近两个端点（它们是各自区间的右端点和左端点）
        #         left_neigh = d.get(rmIdx - 1, [0, 0])
        #         right_neigh = d.get(rmIdx + 1, [0, 0])
        #         # 若存在则合并两个区间为一个大区间
        #         d[rmIdx] = [
        #             left_neigh[0] + right_neigh[0] + 1, # 自己可能是端点
        #             left_neigh[1] + right_neigh[1] + nums[rmIdx],  # 此段区间和
        #         ]
        #         # 每个区间的两端包含该区间长度和区间和信息
        #         d[rmIdx - left_neigh[0]] = d[rmIdx]  # 区间左端点更新 长度和区间和
        #         d[rmIdx + right_neigh[0]] = d[rmIdx]  # 区间右端点更新 长度和区间和

        #         last = max(last, d[rmIdx][1])  # 更新此轮区间和与历史最大区间和的最大值
        #     ans.append(last)
        # ans.reverse()
        # return ans


45800