C++ 100% Faster | Priority Queue | Set | Easy Step By Step Explanation
Intuition\nThe problem requires efficiently maintaining the sum of unmarked elements in an array while processing queries that mark or unmark elements. We can l
# Intuition\nThe problem requires efficiently maintaining the sum of unmarked elements in an array while processing queries that mark or unmark elements. We can leverage a priority queue to keep track of the smallest unmarked elements and a set to store the indices of marked elements.\n\n# Approach\n1. **Initialization:**\n    - Create a priority queue (pq) to store elements (value, index) pairs. Lower values have higher priority.\n    - Use a set (st) to keep track of marked element indices.\n    - Initialize sum to the total sum of elements in nums.\n    - Populate pq with all elements from nums.\n    \n2. **Process Queries:**\n    - **Iterate through each query [idx, k]:**\n        - **Mark Element at Index idx (if unmarked):**\n            - **If idx is not found in st (unmarked), add it to st and subtract its value from sum.**\n        - **Mark k Smallest Unmarked Elements:**\n           - **While k is positive and pq is not empty:**\n                - Dequeue the top element (val, idx2) from pq.\n                - If idx2 is not found in st (unmarked), mark it by adding it to st and subtracting val from sum.\n                - Decrement k to indicate one less element to mark.\n                \n3. **Store Results:**\n    - After processing each query, append the current sum to the ans vector, representing the sum of unmarked elements.\n\n# Complexity\n- Time complexity: **O(n log n + m log n)**\n    - **Initialization (priority queue population):** O(n log n) due to heap operations.\n    - **Query processing:** O(m log n) for dequeuing and potentially marking elements. In the worst case, all m queries might involve marking elements from pq.\n\n- Space complexity: **O(n)**\n    - pq stores up to n elements.\n    - st stores at most n marked element indices.\n\n# Code\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {\n        long long n = nums.size();\n        vector<long long> ans;\n        unordered_set<long long> st;\n        priority_queue<pair<long, long>, vector<pair<long, long>>, greater<pair<long, long>>> pq;  \n\n        for (long long i = 0; i < n; i++) {\n            pq.push({nums[i], i});\n        }\n\n        long long sum = accumulate(nums.begin(), nums.end(), 0LL);  \n\n        for (auto& it : queries) {\n            long long idx = it[0];\n            long long k = it[1];\n\n            \n            if (st.find(idx)==st.end()) {\n                st.insert(idx);\n                sum -= nums[idx];\n            }\n\n            while(k>0 && !pq.empty()){\n                long long val = pq.top().first;\n                long long idx2 = pq.top().second;\n                pq.pop();\n                \n                if(st.find(idx2)==st.end()){\n                    st.insert(idx2);\n                    sum-=val;\n                    k--;\n                }\n            }\n\n            ans.push_back(sum);\n        }\n\n        return ans;\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n\n```\n![Please Upvote3jpeg.png](https://assets.leetcode.com/users/images/ba010e14-74f0-40da-9f1c-d50e5f437cc3_1710603411.1695714.png)\n
['Array', 'Heap (Priority Queue)', 'C++']