[C++] three multisets
idea\n\n store the last m elements in three sets: L, M, R, the sum of elements in M is S\n\n every time we add a new element, besides an insertion operation, we
## idea\n\n* store the last m elements in three sets: `L, M, R`, the sum of elements in M is `S`\n\n* every time we add a new element, besides an insertion operation, we may also need to erase one extra element.\n\n* after the insertion and erasion, adjust L, M; adjust M, R\n\n\t(I added an `int adjust(multiset<int> &a, multiset<int> &b, int n)` function to make set `a`\'s size <= n, and return the difference of sum(a) after the adjustment.)\n\t\n## code\n```c++\ntypedef long long ll;\nclass MKAverage {\nprivate:\n    int m, mm, K;\n    vector<int> A;\n    multiset<int> L, M, R;\n    ll S;\npublic:\n    MKAverage(int m, int k): m(m), mm(m - 2*k), K(k), S(0) {}\n\n    int adjust(multiset<int> &a, multiset<int> &b, int n) {\n        int diff = 0; // sum(a) diff\n        if (a.size() < n) {\n            if (!b.empty()) {\n                auto it = b.begin();\n                diff += *it;\n                a.insert(*it);\n                b.erase(it);\n            }\n        } else if (a.size() > n) {\n            auto it = a.rbegin();\n            diff -= *it;\n            b.insert(*it);\n            a.erase(prev(a.end()));\n        }\n        return diff;\n    }\n    \n    void addElement(int num) {\n        A.push_back(num);\n        if (L.empty() || *L.rbegin() >= num) {\n            L.insert(num);\n        } else if (M.empty() || *M.rbegin() >= num) {\n            M.insert(num);\n            S += num;\n        } else {\n            R.insert(num);\n        }\n        if (A.size() > m) {\n            int v = A[A.size() - 1 - m];\n            if (v <= *L.rbegin()) {\n                L.erase(L.find(v));\n            } else if (v <= *M.rbegin()) {\n                M.erase(M.find(v));\n                S -= v;\n            } else {\n                R.erase(R.find(v));\n            }\n        }\n        S -= adjust(L, M, K);\n        S += adjust(M, R, mm);\n    }\n    \n    int calculateMKAverage() {\n        if (A.size() < m) return -1;\n        return S / mm;\n    }\n};\n```
[]