Python3 solution w/ SortedList, O(logM) add, O(1) calculate
python3 doesn\'t have a built-in order statistic tree or even a basic BST and that may be why sortedcontainers is one of the few third-party libraries allowed.\
python3 doesn\'t have a built-in [order statistic tree](https://en.wikipedia.org/wiki/Order_statistic_tree) or even a basic BST and that may be why `sortedcontainers` is one of the few third-party libraries allowed.\n\nAnyway, with a [SortedList](http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html) this solution is conceptually simple. I use both a deque and a SortedList to keep track of the last m numbers, FIFO. It\'s trivial to maintain the total sum of them. To maintain the sum of the smallest/largest k numbers, we examine the index at which the new number will be inserted into the SortedList and the index at which the oldest number will be removed from the SortedList. If the new number to be inserted will become one of the smallest/largest k numbers, we add it to self.first_k/self.last_k and subtract out the current kth smallest/largest number. The operation for removing the oldest number is similar but the reverse. The only gotcha is the off-by-1 error.\n\n```\nfrom sortedcontainers import SortedList\n\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.m, self.k = m, k\n        self.deque = collections.deque()\n        self.sl = SortedList()\n        self.total = self.first_k = self.last_k = 0\n\n    def addElement(self, num: int) -> None:\n        self.total += num\n        self.deque.append(num)\n        index = self.sl.bisect_left(num)\n        if index < self.k:\n            self.first_k += num\n            if len(self.sl) >= self.k:\n                self.first_k -= self.sl[self.k - 1]\n        if index >= len(self.sl) + 1 - self.k:\n            self.last_k += num\n            if len(self.sl) >= self.k:\n                self.last_k -= self.sl[-self.k]\n        self.sl.add(num)\n        if len(self.deque) > self.m:\n            num = self.deque.popleft()\n            self.total -= num\n            index = self.sl.index(num)\n            if index < self.k:\n                self.first_k -= num\n                self.first_k += self.sl[self.k]\n            elif index >= len(self.sl) - self.k:\n                self.last_k -= num\n                self.last_k += self.sl[-self.k - 1]\n            self.sl.remove(num)\n\n    def calculateMKAverage(self) -> int:\n        if len(self.sl) < self.m:\n            return -1\n        return (self.total - self.first_k - self.last_k) // (self.m - 2 * self.k)\n```\n\nTime complexity: O(logM) add due to operations on the SortedList (essentially an [order statistic tree](https://en.wikipedia.org/wiki/Order_statistic_tree)). O(1) calculate is trivial.\nSpace complexity: O(M) due to the deque and SortedList.
['Queue', 'Python3']