3 multiset and a queue
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n    For average: O(1)\n    For insert: O(log(m))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m)\n\n# Code\n```\nclass MKAverage {\n    multiset<int> low, mid, high;\n    int m, k;\n    long long midSum;\n    int totalElements;\n    queue<int> q;\n\n    bool removeFromSet(int num, multiset<int> &s) {\n        auto it = s.find(num);\n        if(it != s.end()) {\n            s.erase(it);\n            return true;\n        }\n        return false;\n    }\n\n    void remove(int num) {\n        if(removeFromSet(num, low)) {\n            int element = *mid.begin();\n            mid.erase(mid.find(element));\n            midSum -= element;\n            low.insert(element);\n            element = *high.begin();\n            mid.insert(element);\n            midSum += element;\n            high.erase(high.find(element));\n        }\n        else if(removeFromSet(num, mid)) {\n            midSum -= num;\n            int element = *high.begin();\n            mid.insert(element);\n            midSum += element;\n            high.erase(high.find(element));\n            return;\n        }\n        else removeFromSet(num, high);\n    }\n\n    void addUtil(int num) {\n        low.insert(num);\n        if(low.size() > k) {\n            int element = *low.rbegin();\n            low.erase(low.find(element));\n            mid.insert(element);\n            midSum += element;\n        }\n        if(mid.size() > m - 2*k) {\n            int element = *mid.rbegin();\n            mid.erase(mid.find(element));\n            high.insert(element);\n            midSum -= element;\n        }\n    }\n\npublic:\n    MKAverage(int m, int k) {\n        this->m = m;\n        this->k = k;\n        midSum = 0;\n        totalElements = 0;\n    }\n\n    \n    void addElement(int num) {\n        totalElements++;\n        if(totalElements > m) {\n            int element = q.front();\n            q.pop();\n            remove(element);\n            totalElements--;\n        }\n\n        q.push(num);\n        addUtil(num);\n    }\n    \n    int calculateMKAverage() {\n        if(totalElements < m) return -1;\n        return midSum / (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 8272\n 33433\n 15456\n */\n```
['C++']