Multiset | Queue O(logn) Time complexity
Intuition\n- Try to visualize it what are our requirements.\n- Firstly we need to maintain a window of size m so that only latest m elements are considered.\n- 
# Intuition\n- Try to visualize it what are our requirements.\n- Firstly we need to maintain a **window of size m** so that only latest m elements are considered.\n- Which data structure can we think of? yes it\'s **queue** when size exceeds m just pop oldest value and insert latest value.\n- Now our main aim is to actually get the sum also by excluding the **k largest and smallest elements in window**.\n- Now we need the ordering to be sorted right, and a window of m size need to be maintained.\n- Again which data structure comes to your brain? it\'s **priority queue.**\n- but we need smallest and largest values right, also we need to keep track of sum.\n- Now, to find and remove element in priority queue is difficult think of other data structure which works similar to priority queue but also allows you to find the element quicker.\n- Yes, it\'s **Multiset** which stores elements in sorted order and duplicates are also maintained.\n- Now, we create **3 multisets** one is **low of size k mid of size m-2k and high of k**.\n- We keep track of sum of mid multiset for average.\n# Insertion\n- Whenever we try to insert a new value, we will first insert it into **low** if it\'s size exceeds k then we take out the **largest value** in low and insert it into **mid**.\n- Then if size of mid exceeds **m-2k** then take the **largest of mid** and insert it into high.\n- high doesn\'t necessarily have to be of **k size**.\n- while modifying mid set keep track of summation of elements in mid.\n# Deletion\n- We have to remove the oldest value which is popped out by queue from multisets.\n- Firstly, we have to find out in which multiset the value lies.\n- If it is in **low** then we erase it, not size of low is imbalanced, to balance it we take the lowest value from mid and insert it to low.\n- Now, mid size if imbalanced( < m-2k) then we take smallest from high and insert it into mid and erase it from high.\n- Now, if the value is present in **mid** then erase it from mid and take the lowest value from high and insert it into mid, maintain sum of mid accordingly.\n- Now, if the value is present in **high** we remove it. now balancing is done.\n\n# Complexity\n- Time complexity: $$O(logn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass MKAverage {\npublic:\n    multiset<long long> low, mid, high;\n    long long midSum = 0;\n    long long totalcount = 0;\n    queue<long long> que;\n    int m,k;\n    bool removeFromSet(multiset<long long> &se, long long num) {\n        auto iter = se.find(num);\n        if(iter == se.end()) return false;\n        se.erase(iter);\n        return true;\n    }\n    void remove(int num) {\n        if(removeFromSet(low, num)) {\n            //mid to low\n            int element = *mid.begin();\n            low.insert(element);\n            midSum -= element;\n            mid.erase(mid.find(element));\n            //high to mid\n            element = *high.begin();\n            midSum += element;\n            mid.insert(element);\n            high.erase(high.find(element));\n        }\n        else if(removeFromSet(mid, num)) {\n            //high to mid\n            midSum -= num;\n            int element = *high.begin();\n            midSum += element;\n            mid.insert(element);\n            high.erase(high.find(element));\n        }\n        else {\n            removeFromSet(high, num);\n        }\n    }\n\n    void insert_val(int num) {\n        low.insert(num);\n        if(low.size() > k) {\n            int element = *low.rbegin();\n            low.erase(low.find(element));\n            midSum += element;\n            mid.insert(element);\n        }\n        if(mid.size() > m - 2*k) {\n            int element = *mid.rbegin();\n            midSum -= element;\n            mid.erase(mid.find(element));\n            high.insert(element);\n        }\n    }\n    MKAverage(int m, int k) {\n        this->m = m;\n        this->k = k;\n    }\n    \n    void addElement(int num) {\n        que.push(num);\n        insert_val(num);\n        totalcount++;\n        if(totalcount > m) {\n            int n = que.front();\n            remove(n);\n            que.pop();\n            totalcount--;\n        }\n        cout << midSum << endl;\n    }\n    \n    int calculateMKAverage() {\n        if(totalcount < 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```
['C++']