Using multiset iterators
Intuition\n Describe your first thoughts on how to solve this problem. \nKeep elements in a sorted container to easily exclude the k lowest and highest by keepi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nKeep elements in a sorted container to easily exclude the k lowest and highest by keeping track of the sum. Use a queue and some pointers to keep the container updated.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse a multiset to keep track of the m valid elements.\nWhile building, when there are finally m elements, initialize pointers to point to the kth lowest and kth highest element and adjust the sum.\nAs we add and remove elements, maintain the correct pointer position and sum.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\naddElement: $$O(log m)$$\ncalculateMKAverage: $$O(1)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(m)$$\n# Code\n```\nclass MKAverage {\n    int m, k;\n    int64_t sum = 0;\n    std::multiset<int> data;\n    decltype(data)::iterator lo, hi;\n    std::queue<decltype(data)::iterator> q;\npublic:\n    MKAverage(int m, int k) : m{m}, k{k} {\n\n    }\n    \n    void addElement(int num) {\n        q.push(data.insert(num));\n\n        if (q.size() < m) {\n            sum += num;\n            return;\n        }\n        else if (q.size() == m) {\n            sum += num;\n            lo = data.begin(), hi = std::prev(data.end());\n            sum -= *lo + *hi;\n            for (int i = 1; i < k; ++i)\n                lo = std::next(lo),\n                hi = std::prev(hi),\n                sum -= *lo + *hi;\n            return;\n        }\n\n        // Adjust for the entering number\n        if (num >= *hi)\n            sum += *hi, hi = std::next(hi);\n        else if (num < *lo)\n            sum += *lo, lo = std::prev(lo);\n        else\n            sum += num;\n\n        // Adjust for the leaving number\n        if (q.front() == hi || *q.front() > *hi)\n            hi = std::prev(hi), sum -= *hi;\n        else if (q.front() == lo || *q.front() <= *lo)\n            lo = std::next(lo), sum -= *lo;\n        else\n            sum -= *q.front();\n\n        data.erase(q.front());\n        q.pop();\n    }\n    \n    int calculateMKAverage() {\n        if (q.size() < m)\n            return -1;\n\n        return sum / (m - 2 * k);\n    }\n};\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * MKAverage* obj = new MKAverage(m, k);\n * obj->addElement(num);\n * int param_2 = obj->calculateMKAverage();\n */\n```
['C++']