C++ 3 multisets
See my latest update in repo LeetCode\n\n## Solution 1. 3 Multisets\n\n Use 3 multiset<int> to track the top k, bottom k and middle elements.\n Use queue<int> q
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. 3 Multisets\n\n* Use 3 `multiset<int>` to track the top `k`, bottom `k` and middle elements.\n* Use `queue<int> q` to track the current `m` numbers.\n* Use `sum` to track the sum of numbers in `mid`.\n\nPlease see comments as explanations.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-236/problems/finding-mk-average/\n// Author: github.com/lzl124631x\n// Time: \n//     MKAverage: O(1)\n//     addElement: O(logM)\n//     calculateMKAverage: O(1)\n// Space: O(M)\nclass MKAverage {\n    multiset<int> top, bot, mid;\n    queue<int> q;\n    long sum = 0, m, k;\npublic:\n    MKAverage(int m, int k) : m(m), k(k) {}\n    \n    void addElement(int n) {\n        if (q.size() < m) mid.insert(n); // when there are less than `m` numbers, always insert into `mid`.\n        q.push(n);\n        if (q.size() == m) {\n            // when we reached exactly `m` numbers, we nudge numbers from `mid` to `top` and `bot`, and calculate `sum`.\n            for (int i = 0; i < k; ++i) {\n                bot.insert(*mid.begin());\n                mid.erase(mid.begin());\n            }\n            for (int i = 0; i < k; ++i) {\n                top.insert(*mid.rbegin());\n                mid.erase(prev(mid.end()));\n            }\n            for (int x : mid) sum += x;\n        } else if (q.size() > m) {\n            // when we\'ve seen more than `m` numbers. We first add the new number `n` to where it should belong.\n            // If we add `n` to `top` or `bot`, we balance them with `mid` to make sure `top` and `bot` have exactly `k` numbers\n            if (n < *bot.rbegin()) {\n                bot.insert(n);\n                int x = *bot.rbegin();\n                bot.erase(prev(bot.end()));\n                mid.insert(x);\n                sum += x; \n            } else if (n > *top.begin()) {\n                top.insert(n);\n                int x = *top.begin();\n                top.erase(top.begin());\n                mid.insert(x);\n                sum += x;\n            } else {\n                mid.insert(n);\n                sum += n;\n            }\n            // Then we remove the number `rm` that is no longer one of the latest `m` numbers.\n            int rm = q.front();\n            q.pop();\n            auto it = mid.find(rm);\n            if (it != mid.end()) { // first try removing from `mid`, then `top` or `bot`.\n                mid.erase(it);\n                sum -= rm;\n            } else {\n                it = top.find(rm);\n                if (it != top.end()) {\n                    top.erase(it);\n                } else {\n                    bot.erase(bot.find(rm));\n                }\n            }\n            // Lastly, balance `top` and `bot` if needed\n            if (bot.size() < k) {\n                int x = *mid.begin();\n                bot.insert(x);\n                mid.erase(mid.begin());\n                sum -= x;\n            } else if (top.size() < k) {\n                int x = *mid.rbegin();\n                top.insert(x);\n                mid.erase(prev(mid.end()));\n                sum -= x;\n            }\n        }\n    }\n    \n    int calculateMKAverage() {\n        return q.size() == m ? (sum / (m - 2 * k)) : -1;\n    }\n};\n```
[]