C++ Sort index vector | No priority queue | O(NlogN + M)
\nclass Solution {\npublic:\n    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {\n      const int n = nums.size();\n      
```\nclass Solution {\npublic:\n    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {\n      const int n = nums.size();\n      vector<int> indices(n), inv(n);\n      iota(begin(indices), end(indices), 0); // create a vector with n elements with elements {0, 1, ..., n-1}\n\t  // Sort the indices vector such that we preserve the relative order of identical elements\n\t  // i.e. the ordering of indices will give the sorted elements of nums\n\t  // nums[indices[0]] will be the smallest element, nums[indices[n-1]]  will be the largest element\n\t  // if nums[indices[i]] == nums[indices[j]] and i < j, then indices[i] is considered smaller than indices[j]\n      sort(begin(indices), end(indices), [&nums](const auto& a, const auto& b) {\n          return nums[a] == nums[b] ? a < b : nums[a] < nums[b];\n      });\n\n      long long sum = 0LL;\n      for (int i = 0; i < n; i++) {\n\t    // create an inverse mapping so we know which index the element came from\n\t\t// this will be useful as we need to mark a specific index\n        inv[indices[i]] = i; \n        sum += nums[i];\n      }\n\n\t  // Helper functions to check if an index is marked and to get the stored index\n\t  // We mark an index by setting the 20th bit\n      auto markIndex = [&indices](int idx) {\n        indices[idx] |= (1 << 20);\n      };\n      auto isMarked = [&indices](int idx) {\n        return indices[idx] & (1 << 20);\n      };\n\t  // Only look at bits below the 20th bit for the index value\n      auto getIndex = [&indices](int idx) {\n        return 0x000FFFFF & indices[idx];\n      };\n      \n\t  // p is the position of the first (best guess) non marked index in the sorted indices\n      int p = 0;\n      vector<long long> res;\n      for (auto& q : queries) {\n        int idx = q[0], k = q[1];\n\t\t// Mark nums[idx] => mark indices[inv[idx]]\n        if (!isMarked(inv[idx])) {\n          markIndex(inv[idx]);\n          sum -= nums[idx];\n        }\n\t\t// Mark the next k nonmarked elements\n        for (int i = p; i < n && k; i++) {\n          if (!isMarked(i)) {\n            k--;\n            markIndex(i);\n            p = i + 1;\n            sum -= nums[getIndex(i)];\n          } \n        }\n        res.push_back(sum);\n      }\n      return res;\n    }\n};\n```
['Bit Manipulation', 'C']