Naive Java solution with 2 PQs + TreeMap, probably will be TLE soon though
Comments are in line.\n\nI expect this to be TLE soon with more test cases added, but I find this to be naive enough so sharing it.\n\n\nclass MKAverage {\n    
Comments are in line.\n\nI expect this to be TLE soon with more test cases added, but I find this to be naive enough so sharing it.\n\n```\nclass MKAverage {\n    int m;\n    int k;\n    List<Integer> lastM; // Record last m numbers, ordered by when they were added. This is for removing number.\n    TreeMap<Integer, Integer> middle; // Record the numbers in the middle. Remains empty until we have more than 2*k numbers.\n    PriorityQueue<Integer> smallerK;\n    long smallerSum;\n    PriorityQueue<Integer> largerK;\n    long largerSum;\n    long sum;\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n        lastM = new ArrayList<>();\n        middle = new TreeMap<>();\n        smallerK = new PriorityQueue<>((a, b) -> b - a);\n        smallerSum = 0;\n        largerK = new PriorityQueue<>();\n        largerSum = 0;\n        sum = 0;\n    }\n    \n    public void addElement(int num) {\n        /**\n\t\t * First, check if need to remove number.\n\t\t * If yes, remove it from the head of lastM and update total sum.\n\t\t * Also check if need to remove it from middle M, smaller K or larger K, and update smaller sum and larger sum.\n\t\t */\n        if (lastM.size() == m) {\n            int toRemove = lastM.remove(0);\n            sum -= toRemove;\n            if (middle.containsKey(toRemove)) {\n                middle.put(toRemove, middle.get(toRemove) - 1);\n                if (middle.get(toRemove) == 0) {\n                    middle.remove(toRemove);\n                }\n            }\n            \n            if (toRemove <= smallerK.peek()) {\n                smallerK.remove(toRemove);\n                smallerSum -= toRemove;\n                int toOffer = middle.firstKey();\n                middle.put(toOffer, middle.get(toOffer) - 1);\n                if (middle.get(toOffer) == 0) {\n                    middle.remove(toOffer);\n                }\n                smallerK.offer(toOffer);\n                smallerSum += toOffer;\n            } else if (toRemove >= largerK.peek()) {\n                largerK.remove(toRemove);\n                largerSum -= toRemove;\n                int toOffer = middle.lastKey();\n                middle.put(toOffer, middle.get(toOffer) - 1);\n                if (middle.get(toOffer) == 0) {\n                    middle.remove(toOffer);\n                }\n                largerK.offer(toOffer);\n                largerSum += toOffer;\n            }\n        }\n        \n\t\t/**\n\t\t * Add it to the tail of lastM, and update total sum.\n\t\t * Set the number to add to middle m to just be the current num for now, this might change if num is put into either smaller/larger half.\n\t\t */\n        lastM.add(num);\n        int addToMiddle = num;\n        sum += num;\n        if (smallerK.size() < k) {\n\t\t    /**\n\t\t\t * Don\'t have k numbers yet, simply add the number to both halves and update smaller and larger sum.\n\t\t\t */\n            smallerK.offer(num);\n            smallerSum += num;\n            largerK.offer(num);\n            largerSum += num;\n        } else {\n\t\t    /**\n\t\t\t * Have more than k numbers, check whether to put the number to smaller k or larger k.\n\t\t\t * \n\t\t\t * The reason to do both check is that when we don\'t have 2*k numbers, the two halves will overlap,\n\t\t\t * the number may still need to be in both halves.\n\t\t\t * \n\t\t\t * Update the eventual number to be added to middle m.\n\t\t\t */\n            if (num <= smallerK.peek()) {\n                addToMiddle = smallerK.poll();\n                smallerSum -= addToMiddle;\n                smallerK.offer(num);\n                smallerSum += num;\n            }\n            \n            if (num >= largerK.peek()) {\n                addToMiddle = largerK.poll();\n                largerSum -= addToMiddle;\n                largerK.offer(num);\n                largerSum += num;\n            }\n        }\n        \n\t\t/**\n\t\t * Finally, only add to middle m if we have more than 2*k numbers.\n\t\t */\n        if (lastM.size() > 2 * k) {\n            middle.put(addToMiddle, middle.getOrDefault(addToMiddle, 0) + 1);\n        }\n    }\n    \n    public int calculateMKAverage() {\n        if (lastM.size() != m) {\n            return -1;\n        }\n        \n        return (int) ((sum - smallerSum - largerSum) / (m - 2 * k));\n    }\n}\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * MKAverage obj = new MKAverage(m, k);\n * obj.addElement(num);\n * int param_2 = obj.calculateMKAverage();\n */\n```
[]