2382. 删除操作后的最大子段和--(phase2--day3)
2382. 删除操作后的最大子段和
给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询，nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成更小的子段。
一个 子段 是 nums 中连续 正 整数形成的序列。子段和 是子段中所有元素的和。
请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]是第 i 次删除操作以后的 最大 子段和。
**注意：**一个下标至多只会被删除一次。
示例 1：
输入：nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
输出：[14,7,2,2,0]
解释：用 0 表示被删除的元素，答案如下所示：
查询 1 ：删除第 0 个元素，nums 变成 [0,2,5,6,1] ，最大子段和为子段[2,5,6,1] 的和 14 。
查询 2 ：删除第 3 个元素，nums 变成 [0,2,5,0,1] ，最大子段和为子段 [2,5]的和 7 。
查询 3 ：删除第 2 个元素，nums 变成 [0,2,0,0,1] ，最大子段和为子段 [2] 的和 2 。
查询 4 ：删除第 4 个元素，nums 变成 [0,2,0,0,0] ，最大子段和为子段 [2] 的和 2 。
查询 5 ：删除第 1个元素，nums 变成 [0,0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。 所以，我们返回 [14,7,2,2,0] 。
示例 2：
输入：nums = [3,2,11,1], removeQueries = [3,2,1,0]
输出：[16,5,3,0] 解释：用 0
表示被删除的元素，答案如下所示：
查询 1 ：删除第 3 个元素，nums 变成 [3,2,11,0] ，最大子段和为子段 [3,2,11]的和 16 。
查询 2 ：删除第 2 个元素，nums 变成 [3,2,0,0] ，最大子段和为子段 [3,2] 的和 5 。
查询 3：删除第 1 个元素，nums 变成 [3,0,0,0] ，最大子段和为子段 [3] 的和 3 。
查询 4 ：删除第 0 个元素，nums变成 [0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。 所以，我们返回 [16,5,3,0] 。
提示：
n == nums.length == removeQueries.length
1 <= n <= 1e5 1 <= nums[i] <=1e9
0 <= removeQueries[i] < n
removeQueries 中所有数字 互不相同 。
解析：
- 利用反向思考，把删除转化为添加元素（从末尾到开头逐个添加）
- 假如原来元素为 a b c ，现在需要添加c，就需要将b与a、c连接，a、c可能为一个元素集合，可以使用并查集处理集合合并。
- 实际上，我们只需要将b，c（也就是元素x，x+1合并）合并即可（同时利用并查集将其所有元素值合并），不需要向左合并（如果将a、c同时与b合并，那么下次添加a的时候会二次合并b，造成重复）。
- 又怎么能保证abc会作一个子段出现呢？
- 如果a先删除，那么b先添加，bc合并，当添加a的时候也会向右合并把abc合并起来；
- 如果a后删除，那么ab已经合并为一个元素，那么合并bc其实也就是合并ab 与c。因此，只需要向右合并即可。
代码：
lass Solution {
public:
int fa[100001];
// 寻找父节点，状态压缩
int find(int x){
if(fa[x]!=x){
fa[x]=find(fa[x]);
return fa[x];
}
else
return x;
}
vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
int n=nums.size();
// 并查集数组初始化
for(int i=0;i<n+1;i++)
fa[i] = i;
long long sum[n+1];
memset(sum,0,sizeof(sum));
vector<long long> ans(n,0);
for(int i=n-1;i>0;i--){
//cout<<i<<endl;
int x=removeQueries[i];
int to = find(x+1);
fa[x] = to;
// 添加节点更新集合所有元素和的值
sum[to] += nums[x] + sum[x];
// 新的子段，与原有子段最大值的最大值作为此状态下的结果
ans[i-1] = max(ans[i],sum[to]);
}
return ans;
}
};
做法来源：视频讲解