C++| Multisets
Intuition\nUse a Queue to strore elements from the Q, max size of the Q should be m. Use 3 multisets, 1 for smallest K elements, second set for for M-2K mid ele
# Intuition\nUse a Queue to strore elements from the Q, max size of the Q should be m. Use 3 multisets, 1 for smallest K elements, second set for for M-2K mid elements, third set for largest K elements. For every element added, pop Q front if its size > m and then update the sets and sum \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass MKAverage {\npublic:\n    queue<int> mQ;\n    multiset<int> left;\n    multiset<int> center;\n    multiset<int> right;\n    int M;\n    int K;\n    long int mSum;\n    bool mFlag;\n    vector<int> mArr;\n    int mSize;\n    MKAverage(int m, int k) {\n        M = m;\n        K = k;\n        mSum = 0;\n        mFlag = false;\n        mSize = (M-2*K);\n    }\n    \n    void removeFromSet(int num) {\n        if (left.find(num) != left.end()) {\n            left.erase(left.find(num));\n            int val = *center.begin();\n            center.erase(center.find(val));\n            mSum -= val;\n            left.insert(val);\n            val = *right.begin();\n            mSum += val;\n            center.insert(val);\n            right.erase(right.find(val));\n\n        } else if (center.find(num) != center.end()) {\n            center.erase(center.find(num));\n            mSum -= num;\n            int val = *right.begin();\n            mSum += val;\n            center.insert(val);\n            right.erase(right.find(val));\n\n        } else {\n            right.erase(right.find(num));\n        }\n    }\n\n    void addToSet(int num) {\n        left.insert(num);\n        if(left.size()>K) {\n            int val = *left.rbegin();\n            left.erase(left.find(val));\n            center.insert(val);\n            mSum += val;\n        }\n\n        if(center.size()>mSize) {\n            int val = *center.rbegin();\n            mSum -= val;\n            center.erase(center.find(val));\n            right.insert(val);\n        }\n    }\n\n    void addElement(int num) {\n        mQ.push(num);\n        if(mQ.size()>M) {\n            //Remove front element from Q and from the liar\n            int val = mQ.front();\n            mQ.pop();\n            removeFromSet(val);\n        }\n        //Add num to set\n        addToSet(num);\n    }\n    \n    int calculateMKAverage() {\n        if(mQ.size()<M)\n            return -1;\n\n        return mSum/mSize;\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++']