C++ Balance 3 Multisets
A bit lengthy; the idea is to keep track of the left, mid, and right sets. When removing or adding numbers, we reballance these sets so that the size of left an
A bit lengthy; the idea is to keep track of the `left`, `mid`, and `right` sets. When removing or adding numbers, we reballance these sets so that the size of `left` and `right` stays `k`.\n\nAlso, we keep track of `sum` for elements in `mid`. That way, the calculate function is O(1).\n \nFinally, to track the current `m` numbers, we use a circular array of size `m`.\n\n```cpp\nint m = 0, k = 0, sz = 0, pos = 0;\nlong sum = 0;\nvector<int> v;\nmultiset<int> left, mid, right;\nvoid remove(int n) {\n    if (n <= *rbegin(left))\n        left.erase(left.find(n));\n    else if (n <= *rbegin(mid)) {\n       auto it = mid.find(n); \n       sum -= *it;\n       mid.erase(it);\n    }\n    else\n        right.erase(right.find(n));\n    if (left.size() < k) {\n        left.insert(*begin(mid));\n        sum -= *begin(mid);\n        mid.erase(begin(mid));\n    }\n    if (mid.size() < sz) {\n        mid.insert(*begin(right));\n        sum += *begin(right);\n        right.erase(begin(right));\n    }\n}\nvoid add(int n) {\n    left.insert(n);\n    if (left.size() > k) {\n        auto it = prev(end(left));\n        mid.insert(*it);\n        sum += *it;\n        left.erase(it);\n    }\n    if (mid.size() > sz) {\n        auto it = prev(end(mid));\n        sum -= *it;\n        right.insert(*it);\n        mid.erase(it);\n    }\n}\nMKAverage(int m, int k) : m(m), k(k), sz(m - 2 * k) {\n    v = vector<int>(m);\n}\nvoid addElement(int num) {\n    if (pos >= m)\n        remove(v[pos % m]);\n    add(num);\n    v[pos++ % m] = num;\n}\nint calculateMKAverage() {\n    if (pos < m)\n        return -1;\n    return sum / sz;\n}\n```
[]