Maximum Segment Sum After Removals (IMPORTANT)

https://leetcode.com/problems/maximum-segment-sum-after-removals/

You are given two 0-indexed integer arrays nums and removeQueries, both of length n. For the ith query, the element in nums at the index removeQueries[i] is removed, splitting nums into different segments.
A segment is a contiguous sequence of positive integers in nums. A segment sum is the sum of every element in a segment.
Return an integer array answer, of length n, where answer[i] is the maximum segment sum after applying the ith removal.
Note: The same index will not be removed more than once.



Example 1:

Input: nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
Output: [14,7,2,2,0]
Explanation: 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].

Example 2:

Input: nums = [3,2,11,1], removeQueries = [3,2,1,0]
Output: [16,5,3,0]
Explanation: 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].


Constraints:

n == nums.length == removeQueries.length
1 <= n <= 10^5
1 <= nums[i] <= 10^9
0 <= removeQueries[i] < n
All the values of removeQueries are unique.

---------------------------------------------------------------------------------------------------------------------------------------

USING MULTISET AND SETS AND SIMULATION

class Solution {
private:
    multiset<long long> sums;
    set<pair<int,int>> ranges;
    vector<long long> prefix;
    int n;
public:
    void SLICE_AND_DICE(set<pair<int,int>>::iterator &itr, vector<int> &nums, int index){
        int start=itr->first;
        int end=itr->second;

        ranges.erase(itr);
        sums.erase(sums.find(prefix[end]-prefix[start]+nums[start]));

        // breaking down {start,end} -> {start,index-1} , {index+1,end}
        if(index-1>=start){
            sums.insert({prefix[index-1]-prefix[start]+nums[start]});
            ranges.insert({start,index-1});
        }
        if(index+1<=end){
            sums.insert({prefix[end]-prefix[index+1]+nums[index+1]});
            ranges.insert({index+1,end});
        }
    }

    vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
        n=nums.size();
        prefix.resize(n);

        for(int i=0;i<n;i++){
            prefix[i]=nums[i];
        }
        for(int i=1;i<n;i++){
            prefix[i]+=prefix[i-1];
        }

        sums.insert(prefix[n-1]);
        sums.insert(0); // incase the whole sums multiset becomes empty, answer is 0
        ranges.insert({0,n-1});

        vector<long long> res;
        for(auto index: removeQueries){
            auto itr=ranges.upper_bound({index,INT_MAX});
            if(itr!=ranges.begin()){
                itr--;
                SLICE_AND_DICE(itr,nums,index);
            }
            else if(itr!=ranges.end()){
                SLICE_AND_DICE(itr,nums,index);
            }
            res.push_back(*sums.rbegin());
        }
        return res;
    }
};  // SIMULATION USING MULTISET AND SETS

---------------------------------------------------------------------------------------------------------------------------------------

USING SEGMENT TREE WITH PREFIX SUFFIX SUM

struct Module{
    long long prefix;
    long long suffix;
    long long segMX;
    long long sum;
};

class Solution {
private:
    Module tree[4*100000+5];
public:
    Module merger(Module &left, Module &right){
        Module res;
        res.prefix=max(left.prefix,left.sum+right.prefix);
        res.suffix=max(right.suffix,right.sum+left.suffix);
        res.sum=left.sum+right.sum;
        res.segMX=max({right.segMX,left.segMX,left.suffix+right.prefix});
        return res;
    }

    void build(vector<int> &nums, int start, int end, int parent){
        if(start==end){
            tree[parent]={nums[start],nums[start],nums[start],nums[start]};
            return;
        }
        int mid=(start+end)/2;
        build(nums,start,mid,2*parent+1);
        build(nums,mid+1,end,2*parent+2);
        tree[parent]=merger(tree[2*parent+1],tree[2*parent+2]);
    }

    void update(int start, int end, int parent, int index, long long int val){
        if(start>end){
            return;
        }
        if(start==end){
            tree[parent]={val,val,val,val};
            return;
        }
        int mid=(start+end)/2;
        if(mid>=index){
            update(start,mid,2*parent+1,index,val);
        }
        else{
            update(mid+1,end,2*parent+2,index,val);
        }
        tree[parent]=merger(tree[2*parent+1],tree[2*parent+2]);
    }

    vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
        int n=nums.size();
        build(nums,0,n-1,0);
        vector<long long> res;
        for(auto q: removeQueries){
            update(0,n-1,0,q,-1e14/2);
            res.push_back(max(0ll,tree[0].segMX));
        }
        return res;
    }
};