Python using SortedList add in O(N) calculate in O(1)
Use 3 SortedList left, mid, right to maintain the smallest k elements, mid part and the biggest k elements seperately. \nWe can do insert, delete, search operat
Use 3 SortedList `left`, `mid`, `right` to maintain the smallest k elements, mid part and the biggest k elements seperately. \nWe can do insert, delete, search operations in SortedList in O(logN). It\'s somehow like TreeSet/TreeMap in Java(but SortedList can store duplicate elements) and MultiSet in C++.\n```\nfrom sortedcontainers import SortedList\nclass MKAverage:\n    # T:O(1) for calculateMKAverage O(Log(N)) for addElement\n    def __init__(self, m: int, k: int):\n        self.queue = collections.deque();\n        self.m = m\n        self.k = k\n        self.N = m-2*k #numbers needed to calculate MKAve\n        self.sum = 0\n        self.left = SortedList()\n        self.mid = SortedList()\n        self.right = SortedList()\n\n    def addElement(self, num: int) -> None:\n        if (len(self.queue)==self.m):\n            self.remove(self.queue[0])\n            self.queue.popleft()\n        self.queue.append(num)\n        self.add(num)\n\n    def calculateMKAverage(self) -> int:\n        if len(self.queue)<self.m:\n            return -1\n        else:\n            return self.sum//self.N\n    def add(self, x):\n        self.left.add(x)\n        if len(self.left)>self.k:\n            mxLeft = self.left.pop()\n            self.sum+=mxLeft\n            self.mid.add(mxLeft)\n        if len(self.mid)>self.N:\n            mxMid = self.mid.pop()\n            self.sum-=mxMid\n            self.right.add(mxMid)\n            \n    def remove(self, x):\n        if x<=self.left[-1]:\n            self.left.remove(x)\n        elif x<=self.mid[-1]:\n            self.sum-=x\n            self.mid.remove(x)\n        else:\n            self.right.remove(x)\n        if len(self.left)<self.k:\n            mnMid = self.mid.pop(0)\n            self.sum-=mnMid\n            self.left.add(mnMid)\n        if len(self.mid)<self.N:\n            mnRight = self.right.pop(0)\n            self.sum+=mnRight\n            self.mid.add(mnRight)\n```
[]