Segment Tree (with Lazy Update, needed for last few test cases)
Intuition\nThe size constraints rule out an O(n^2) solution.\nFirst thoughts were to use a Binary Search, but the range updates pointed strongly to segment tree
# Intuition\nThe size constraints rule out an O(n^2) solution.\nFirst thoughts were to use a Binary Search, but the range updates pointed strongly to segment trees.\nHave attached an LLM generated documentation of the code I wrote below -\n\n\nThe class `Solution` contains:\n\t\u2022\tPrivate Members:\n\t\u2022\t`vector<int> seg`: This is the segment tree array that stores the maximum values for segments of the input array.\n\t\u2022\t`vector<int> lseg`: This is the lazy propagation array that helps manage delayed updates to ranges in the segment tree.\n\nKey Functions\n\t1.\t`buildTree`:\n\t\u2022\tThis function constructs the segment tree.\n\t\u2022\tIt recursively divides the array into segments and computes the maximum value for each segment.\n\t\u2022\tThe base case occurs when `low` equals `high`, meaning it has reached a leaf node, and it assigns the corresponding value from `nums`.\n\t2.\t`lazyupdate`:\n\t\u2022\tThis function applies any pending updates stored in the `lseg` array to the segment tree.\n\t\u2022\tIf there are pending updates (i.e., `lsegindex != 0`), it updates the current segment\u2019s value and propagates the update to its children if necessary.\n\t3.\t`update`:\n\t\u2022\tThis function updates a range of indices in the segment tree.\n\t\u2022\tIt first calls `lazyupdate` to apply any pending updates.\n\t\u2022\tIf the update range (`ll`, `hh`) does not overlap with the current segment (`low`, `high`), it returns early.\n\t\u2022\tIf the current segment is fully within the update range, it decrements the segment value and marks its children for lazy updates.\n\t\u2022\tIf only part of the current segment is within the update range, it recursively updates its left and right children.\n\t4.\t`val`:\n\t\u2022\tThis function retrieves the value at a specific index in the original array while applying any pending updates.\n\t\u2022\tIt checks if the index is out of bounds and then applies lazy updates before returning the value.\n\t5.\t`numVal`:\n\t\u2022\tA convenience function that calls `val` with appropriate parameters to get the value at a specific index.\n\t6.\t`maxRemoval`:\n\t\u2022\tThis is the main function that processes a series of queries on an input array `nums`.\n\t\u2022\tIt initializes the segment tree and sorts queries based on their first element.\n\t\u2022\tIt uses a priority queue to manage ranges for removal based on queries.\n\t\u2022\tThe outer loop iterates through each index of `nums`, while inner loops handle adding new queries to the priority queue and updating segments until all possible removals are completed or no more valid removals can be made.\n\nDetailed Explanation of `maxRemoval`\n\t\u2022\tThe function starts by initializing the segment tree and lazy propagation arrays based on the size of `nums`.\n\t\u2022\tIt sorts queries in ascending order based on their starting index.\n\t\u2022\tA priority queue is used to manage end indices of queries, allowing efficient access to which ranges can be processed for removal.\n\t\u2022\tThe outer loop iterates over each index in `nums`, checking if there are any queries that can be processed at that index.\n\t\u2022\tFor each index, while there are still values greater than zero (indicating elements that can be removed), it pops from the priority queue and applies updates to decrement those elements in that range, marking them as removed.\n\t\u2022\tThe process continues until either all elements are removed or no more valid removals can be made.\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    vector<int> seg;\n    vector<int> lseg;\npublic:\n    void buildTree(int index, int low, int high, vector<int>& nums){\n        if(low==high){\n            seg[index] = nums[low];\n            return;\n        }\n        int mid = (low+high)/2;\n        buildTree(2*index+1, low, mid, nums);\n        buildTree(2*index+2, mid+1, high, nums);\n        seg[index] = max(seg[2*index+1], seg[2*index+2]);\n    }\n    void lazyupdate(int index, int low, int high){\n        if(lseg[index]!=0){\n            seg[index] -= lseg[index];\n            if(low!=high){\n                lseg[2*index+1] += lseg[index];\n                lseg[2*index+2] += lseg[index];\n            }\n            lseg[index]=0;\n        }\n    }\n    void update(int index, int low, int high, int ll, int hh){\n        lazyupdate(index, low, high);\n        if(ll>high || hh<low) return;\n        if(low==high){\n            seg[index] = seg[index]-1;\n            return;\n        }\n        if(low>=ll && high<=hh){\n            seg[index]-=1;\n            lseg[2*index+1]+=1;\n            lseg[2*index+2]+=1;\n            return;\n        }\n        int mid = (low+high)/2;\n        update(2*index+1, low, mid, ll, hh);\n        update(2*index+2, mid+1, high, ll, hh);\n        seg[index] = max(seg[2*index+1], seg[2*index+2]);\n        return;\n    }\n    int val(int index, int low, int high, int idx){\n        lazyupdate(index, low, high);\n        if(idx<low || idx>high) return INT_MAX;\n        if(low==high && low==idx){\n            return seg[index];\n        }\n        int mid = (low+high)/2;\n        int left = val(2*index+1, low, mid, idx);\n        int right = val(2*index+2, mid+1, high, idx);\n        return right==INT_MAX ? left : right;\n    }\n    int numVal(int idx, int n){\n        return val(0, 0, n-1, idx);\n    }\n    int maxRemoval(vector<int>& nums, vector<vector<int>>& q) {\n        int n = nums.size();\n        seg = vector<int>(4*n + 1, 0);\n        lseg = vector<int>(4*n + 1, 0);\n        buildTree(0, 0, n-1, nums);\n        sort(q.begin(), q.end());\n        priority_queue<int> pq;\n        int count = q.size();\n        int index = 0;\n        int qi = 0;\n        cout<<"qsize"<<q.size()<<endl;\n        while(index<nums.size()){\n            while(qi<q.size() && q[qi][0]<=index){\n                pq.push(q[qi][1]);\n                qi++;\n            }\n            while(numVal(index, n)>0){\n                if(pq.empty()) return -1;\n                int r = pq.top(); pq.pop();\n                if(r<index){\n                    continue;\n                }\n                update(0, 0, n-1, index, r);\n                // for(int i=0; i<n; i++){\n                //     cout<<numVal(i, n)<<" ";\n                // }\n                // cout<<endl;\n                count--;\n            }\n            index++;\n        }\n        return count;\n    }\n};\n```
['C++']