Python3 1 SortedList solution & C++ 3 set solution
Intuition\r\n Describe your first thoughts on how to solve this problem. \r\nThis is a very nice problem to test your ability to analyze what data structure is 
# Intuition\r\n<!-- Describe your first thoughts on how to solve this problem. -->\r\nThis is a very nice problem to test your ability to analyze what data structure is needed, how to design a working system, what data structure different languages provides and their limitations.\r\n# Approach\r\n<!-- Describe your approach to solving the problem. -->\r\nIf you use Python, the sortedcontainer modules will do this very simplistically, because it can both bisect and arrive at element by index in log(N) time.\r\nI tried looking up documentation of C# sorted set, Microsoft so far does not support giving you the iterator inside a sorted set. So you cannot solve the problem in C#.\r\nFor C++, 3 std::set would suffice.\r\n# Complexity\r\n- Time complexity:\r\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\r\n$$O(n log n)$$\r\n- Space complexity:\r\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\r\n$$O(n)$$\r\n# Code\r\nPython3:\r\n```\r\nfrom collections import deque\r\nimport sortedcontainers\r\nclass MKAverage:\r\n    \'\'\'\r\n    Break down the task in hand:\r\n    We want to keep m last numbers in check, have these numbers sorted, such that the top and bottom k elements can be accessed quickly. \r\n    But we also want to update the tree regularly. We cannot afford to calculate the largest and smallest k - sums every time a query is make, so we need to maintain the left and right sums. \r\n    When a new number nums[i] comes in, we first find where is nums[i - m]. This node we must remove. We identify if it is in the left and right k sums, and if so, deduct it from the sums. Note that we also need to add the kth smallest element and the m - k th smallest element. Also, we need to deduct it from the total sum.\r\n    Then we insert nums[i]. We first ask where the insertion position should be, and update the two k sums and totalSum in similar manner as before\r\n\r\n    When calculateMKAverage is called, we just return (totalSum - leftkSum - rightkSum) // (m - 2 * k)\r\n    \'\'\'\r\n    def __init__(self, m: int, k: int):\r\n        self.tree = sortedcontainers.SortedList()\r\n        self.Total = 0\r\n        self.leftSum = 0\r\n        self.rightSum = 0\r\n        self.index = -1\r\n        self.m = m\r\n        self.k = k\r\n        self.dq = deque()\r\n    \r\n    def deleteNode(self, num, ind):\r\n        treeIndex = self.tree.index([num, ind])\r\n        if treeIndex < self.k:\r\n            self.leftSum -= num\r\n            self.leftSum += self.tree[self.k][0]\r\n        if len(self.dq) + 1 - treeIndex <= self.k:\r\n            self.rightSum -= num\r\n            self.rightSum += self.tree[len(self.dq) + 1 - self.k - 1][0]\r\n        self.tree.remove([num, ind])\r\n        self.Total -= num\r\n    \r\n    def insertNode(self, num, ind):\r\n        self.tree.add([num, ind])\r\n        treeIndex = self.tree.bisect_left([num, ind])\r\n        if treeIndex < self.k:\r\n            self.leftSum += num\r\n            if len(self.dq) > self.k:\r\n                self.leftSum -= self.tree[self.k][0]\r\n        if len(self.dq) - treeIndex <= self.k:\r\n            self.rightSum += num\r\n            if len(self.dq) > self.k:\r\n                self.rightSum -= self.tree[len(self.dq) - self.k - 1][0]\r\n        self.Total += num\r\n        \r\n    def addElement(self, num: int) -> None:\r\n        self.index += 1\r\n        if len(self.dq) == self.m:\r\n            value, index = self.dq.popleft()\r\n            self.deleteNode(value, index)\r\n        self.dq.append([num, self.index])\r\n        self.insertNode(num, self.index)\r\n\r\n    def calculateMKAverage(self) -> int:\r\n        return -1 if len(self.tree) < self.m else (self.Total - self.leftSum - self.rightSum) // (self.m - 2 * self.k)\r\n\r\n# Your MKAverage object will be instantiated and called as such:\r\n# obj = MKAverage(m, k)\r\n# obj.addElement(num)\r\n# param_2 = obj.calculateMKAverage()\r\n```\r\nC++:\r\n```\r\n#include <queue>\r\n#include <set>\r\nusing namespace std;\r\n\r\nclass MKAverage {\r\n/*\r\n    We use two sets of size k and one set of size m to store the nodes. When we delete a previous node, we first check if it is in the left and right trees. If so, update the trees.\r\n*/\r\nprivate:\r\n    set<pair<int, int>> tree;\r\n    set<pair<int, int>> left;\r\n    set<pair<int, int>> right;\r\n    long long Total;\r\n    long long leftSum;\r\n    long long rightSum;\r\n    int index;\r\n    int m;\r\n    int k;\r\n    queue<pair<int, int>> q;\r\n\r\n    void deleteNode(int num, int index)\r\n    {\r\n        pair<int, int> nodeToRemove = make_pair(num, index);\r\n        if (left.find(nodeToRemove) != left.end())\r\n        {\r\n            pair<int, int> nodeToInsert = *next(tree.find(*left.rbegin()), 1);\r\n            left.insert(nodeToInsert);\r\n            leftSum -= (long long)num;\r\n            leftSum += (long long)nodeToInsert.first;\r\n            left.erase(nodeToRemove);\r\n        }\r\n        if (right.find(nodeToRemove) != right.end())\r\n        {\r\n            pair<int, int> nodeToInsert = *prev(tree.find(*right.begin()), 1);\r\n            right.insert(nodeToInsert);\r\n            rightSum -= (long long)num;\r\n            rightSum += (long long)nodeToInsert.first;\r\n            right.erase(nodeToRemove);\r\n        }\r\n\r\n        tree.erase(nodeToRemove);\r\n        Total -= (long long)num;\r\n    }\r\n\r\n    void insertNode(int num, int index)\r\n    {\r\n        pair<int, int> nodeToInsert = make_pair(num, index);\r\n        if (left.size() < k || left.lower_bound(nodeToInsert) != left.end())\r\n        {\r\n            if (left.size() == k)\r\n            {\r\n                pair<int, int> nodeToRemove = *left.rbegin();\r\n                left.erase(nodeToRemove);\r\n                leftSum -= (long long)nodeToRemove.first;                                \r\n            }\r\n            left.insert(nodeToInsert);\r\n            leftSum += (long long)num;\r\n         \r\n        }\r\n        if (right.size() < k || right.upper_bound(nodeToInsert) != right.begin())\r\n        {\r\n            if (right.size() == k)\r\n            {\r\n                pair<int, int> nodeToRemove = *right.begin();\r\n                right.erase(nodeToRemove);\r\n                rightSum -= (long long)nodeToRemove.first;                             \r\n            }\r\n            right.insert(nodeToInsert);\r\n            rightSum += (long long)num;            \r\n        }\r\n\r\n        tree.insert(nodeToInsert);\r\n        Total += (long long)num;\r\n    }\r\n\r\npublic:\r\n    MKAverage(int m, int k) {\r\n        tree = set<pair<int, int>>{};\r\n        left = set<pair<int, int>>{};\r\n        right = set<pair<int, int>>{};\r\n        q = queue<pair<int, int>>{};\r\n        Total = (long long)0;\r\n        leftSum = (long long)0;\r\n        rightSum = (long long)0;\r\n        index = -1;\r\n        this->m = m;\r\n        this->k = k;\r\n    }\r\n\r\n    void addElement(int num) {\r\n        index++;\r\n        if (q.size() == m)\r\n        {\r\n            pair<int, int> element = q.front();\r\n            q.pop();\r\n            deleteNode(element.first, element.second);\r\n        }\r\n        q.push(make_pair(num, index));\r\n        insertNode(num, index);\r\n    }\r\n\r\n    int calculateMKAverage() {\r\n        return tree.size() < m ? -1 : (Total - leftSum - rightSum) / (long long)(m - 2 * k);\r\n    }\r\n};\r\n```
['C++', 'Python3']