[Python 3] O(logm) LazySumHeap and PartitionSum
\nclass LazySumHeap:\n    \n    def __init__(self, key):\n        self.heap = []\n        self.key = key\n        self.c = Counter()\n        self.sz = 0\n     
```\nclass LazySumHeap:\n    \n    def __init__(self, key):\n        self.heap = []\n        self.key = key\n        self.c = Counter()\n        self.sz = 0\n        self.sum = 0\n    \n    def __len__(self):\n        return self.sz\n    \n    def clean(self):\n        while self.heap and not self.c[self.heap[0][2]]:\n            heappop(self.heap)\n    \n    def peek(self):\n        self.clean()\n        return self.heap[0][2]\n    \n    def pop(self):\n        self.clean()\n        \n        ret = heappop(self.heap)[2]\n        \n        self.c[ret] -= 1\n        self.sz -= 1\n        self.sum -= ret\n        \n        return ret\n    \n    def remove(self, x):\n        self.c[x] -= 1\n        self.sz -= 1\n        self.sum -= x\n    \n    def push(self, x):\n        \n        entry = [self.key(x), id(x), x]\n        \n        heappush(self.heap, entry)\n        \n        self.c[x] += 1\n        self.sz += 1\n        self.sum += x\n        \n        \nclass PartitionSum:\n    \n    # lowest <= k elements\n    def __init__(self, k):\n        self.k = k\n        self.lo = LazySumHeap(lambda x:-x)\n        self.hi = LazySumHeap(lambda x:x)\n    \n    def rebalance(self):\n        \n        while len(self.lo) > self.k:\n            self.hi.push(self.lo.pop())\n        \n        while self.hi and len(self.lo) < self.k:\n            self.lo.push(self.hi.pop())\n    \n    def add(self, x):\n        \n        if not self.hi or (self.hi and x < self.hi.peek()):\n            self.lo.push(x)\n        else:\n            self.hi.push(x)\n\n        self.rebalance()\n    \n    def remove(self, x):\n        \n        if x <= self.lo.peek():\n            self.lo.remove(x)\n        else:\n            self.hi.remove(x)\n        \n        self.rebalance()\n\n\nclass MKAverage:\n\n    def __init__(self, M: int, K: int):\n        global m,k,q,lo,hi\n        \n        m = M\n        k = K\n        \n        q = deque()\n        \n        lo = PartitionSum(k)\n        hi = PartitionSum(m-k)\n        \n\n    def addElement(self, x: int) -> None:\n        global m,k,q,lo,hi\n        \n        if len(q) <= m-1:\n            q.append(x)\n            lo.add(x)\n            hi.add(x)\n            \n        else:\n            \n            y = q.popleft()\n            lo.remove(y)\n            hi.remove(y)\n            \n            q.append(x)\n            lo.add(x)\n            hi.add(x)\n\n    def calculateMKAverage(self) -> int:\n        global m,k,q,lo,hi\n        \n        if len(q) < m:\n            return -1\n        else:\n            return (lo.hi.sum - hi.hi.sum) // (m-k-k)\n```
[]