[Python] Queue and Binary Search, add O(log m), average O(1)
\nimport bisect\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.list = [] ##Used as a sorted 
```\nimport bisect\nclass MKAverage:\n\n    def __init__(self, m: int, k: int):\n        self.m = m\n        self.k = k\n        self.list = [] ##Used as a sorted list. Elements are sorted in non decreasing order\n        self.added = [] ##Used as a queue\n        self.sum = None\n\t\t\n    def addElement(self, num: int) -> None:\n        ln = len(self.list)\n        if ln < self.m:\n            self.added.append(num)\n            index = bisect.bisect_right(self.list, num)\n            self.list.insert(index, num)\n            if len(self.list) == self.m:\n                self.sum = sum(self.list[self.k:self.m-self.k])\n        else:\n\t\t\t## Pop the element to get the last m-1 elements added\n            x = self.added.pop(0)\n            self.added.append(num)\n            pop_index = bisect.bisect_left(self.list, x)\n            if pop_index<self.k:\n                self.sum -= self.list[self.k]\n            elif pop_index >= self.m-self.k:\n                self.sum -= self.list[self.m-self.k-1]\n            else:\n                self.sum -= x\n            self.list.pop(pop_index)\n\t\t\t\n\t\t\t##Get the index of the new element to be added in the sorted list\n            add_index = bisect.bisect_right(self.list, num)\n            self.list.insert(add_index, num)\n            if add_index<self.k:\n                self.sum += self.list[self.k]\n            elif add_index >= self.m-self.k:\n                self.sum += self.list[self.m-self.k-1]\n            else:\n                self.sum += num\n\n    def calculateMKAverage(self) -> int:\n        if len(self.list)<self.m:\n            return -1\n        else:\n            return self.sum//(self.m - 2*self.k)\n```
[]