C++ Solution Using Only 1 Multiset
Intuition\nmost solutions use 3 multisets, but actually 1 is enough.\n\nBasically we need a queue of size m to support the sliding window. We also want the elem
# Intuition\nmost solutions use 3 multisets, but actually 1 is enough.\n\nBasically we need a queue of size `m` to support the sliding window. We also want the elements inside the window to be sorted so that we can get the middle elements. To support this, We use another multiset (C++ STL\'s implementation of binary search tree) to maintain the queue elements\' order.\n\n# Approach\n\nFirst trick is that we store the multiset\'s iterator in the queue so that we can remove an element both from the queue and multiset easily.\n\nSecond trick is that we store the `start` and `end` iterator of the multiset pointing to the `k`th and `n-k`th (0-indexed) element of the sliding window. We always keep this invariant by updating `start` and `end` when we insert/delete from the sliding window.\n\nThe hard part is how to update `start` and `end` correctly. Imaging the follwing sorted list represented by the multiset (m = 10, k = 2)\n\n```\n[1,2,2,3,4,5,5,6]\n     ^     ^\n   start  end\n```\n\nIf there are elements of same value in the sorted list, c++ multiset guaranteeds to insert the new element to the end of the range. So if a 5 is to be inserted, it will be inserted after the last 5 (the 5 right before 6). c++ multiset also guarantees that the first element in the range of same values will be removed when we delete. E.g. if we remove 5 from the sliding window, it is the first 5 (the 5 right after 4) that is to be removed. This helps produce the following update logic:\n\n- when insert: we move `start` left if `num < *start`, we move `end` right if `num >= *end`\n- when delete: we move `start` right if `num <= *start`. The tricky part is in `end`, in addition to move `end` left when `num > *end`, we also have to move `end` left if `num == *end` and `end` points to the first number in the range (when we delete 5 in the case above).\n\nFinally we keep and update the sum of middle elements in each `addElement` to make `calculateMKAverage` constant time.\n\n\n# Complexity\n\n- Time complexity: `addElement` $$O(log(m))$$, `calculateMKAverage` $$O(1)$$\n- Space complexity: $$O(m)$$\n\n\n# Code\n\n```\nclass MKAverage {\n    multiset<int> mset_;\n    multiset<int>::iterator start_, end_;\n    long long total_ = 0;\n\n    queue<multiset<int>::iterator> que_;\n\n    int m_, k_;\npublic:\n    MKAverage(int m, int k) {\n        m_ = m;\n        k_ = k;\n    }\n    \n    void addElement(int num) {\n        auto it = mset_.insert(num);\n        que_.push(it);\n        if (que_.size() <= 2 * k_) {\n            return;\n        }\n        // first time reaching 2k + 1 elements, initialize start,\n        // end and total\n        if (que_.size() == 2 * k_ + 1) {\n            start_ = mset_.begin();\n            for (int i = 0; i < k_; ++i) {\n                ++start_;\n            }\n            end_ = start_;\n            total_ = *start_;\n            return;\n        }\n        // push, keep the invariant that start and end point to\n        // the kth and (n-k)th elements\n        if (num < *start_) {\n            total_ += *(--start_);\n        } else if (num >= *end_) {\n            total_ += *(++end_);\n        } else {\n            total_ += num;\n        }\n        // pop, keep the invariant as well, special logic for end\n        if (que_.size() > m_) {\n            auto remove = que_.front();\n            if (*remove <= *start_) {\n                total_ -= *(start_++);\n            } else if (*remove > *end_ || remove == end_) {\n                total_ -= *(end_--);\n            } else {\n                total_ -= *remove;\n            }\n            mset_.erase(que_.front());\n            que_.pop();\n        }\n    }\n    \n    int calculateMKAverage() {\n        return que_.size() < m_ ? -1 : total_ / (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++']