balanceSets.cpp

void balanceSets() {
    // from left to mid, elements move in to the mid
    sum += balanceLR(left, mid, k);
    // from mid to right, elements move out from the mid
    sum -= balanceLR(mid, right, m - 2 * k);
}

int balanceLR(multiset<int> &l, multiset<int> &r, int n) {
    // tracks how much should the running sum change in value
    int diff = 0;
    // keep the l's size at n
    while (l.size() > n) {
        int lmax = *l.rbegin();
        diff += lmax;
        l.erase(l.find(lmax));
        r.insert(lmax);
    }
    // keep l smaller than r
    if (*l.rbegin() > *r.begin()) {
        int lmax = *l.rbegin();
        int rmin = *r.begin();
        diff += rmin - lmax;
        l.insert(rmin);
        l.erase(l.find(lmax));
        r.insert(lmax);
        r.erase(r.find(rmin));
    }
    return diff;
}

deleteElement.cpp

void deleteElement(int n) {
    // find(n) is required to delete a single element. 
    // Otherwise, all elements with the same value are deleted.
    if (left.count(n)) {
        left.erase(left.find(n));
    } else if (mid.count(n)) {
        sum -= n; // if the number is deleted from the mid set
        mid.erase(mid.find(n));
    } else {
        right.erase(right.find(n));
    }
}

findingMKAverage.cpp

class MKAverage {
public:
    int m, k, sum;
    queue<int> q;
    multiset<int> left, mid, right;
    MKAverage(int m, int k) : m(m), k(k), sum(0) {}
    
    void addElement(int num) {
        q.push(num);
        left.insert(num);
        if (q.size() > m) {
            remove(q.front());
            q.pop();
        }
    }
    
    void remove(int n) {
        // find(n) is required to delete a single element. 
        // Otherwise, all elements with the same value are deleted.
        if (left.count(n)) {
            left.erase(left.find(n));
        } else if (mid.count(n)) {
            sum -= n; // if the number is deleted from the mid set
            mid.erase(mid.find(n));
        } else {
            right.erase(right.find(n));
        }
    }
    
    void balanceSets() {
        // from left to mid, elements move in to the mid
        sum += balanceLR(left, mid, k);
        // from mid to right, elements move out from the mid
        sum -= balanceLR(mid, right, m - 2 * k);
    }

    int balanceLR(multiset<int> &l, multiset<int> &r, int n) {
        // tracks how much should the running sum change in value
        int diff = 0;
        // keep the l's size at n
        while (l.size() > n) {
            int lmax = *l.rbegin();
            diff += lmax;
            l.erase(l.find(lmax));
            r.insert(lmax);
        }
        // keep l smaller than r
        if (*l.rbegin() > *r.begin()) {
            int lmax = *l.rbegin();
            int rmin = *r.begin();
            diff += lmax - rmin;
            l.insert(rmin);
            l.erase(l.find(lmax));
            r.insert(lmax);
            r.erase(r.find(rmin));
        }
        return diff;
    }
    
    int calculateMKAverage() {
        if (q.size() < m) return -1;
        balanceSets();
        return sum / (m - k * 2);
    }
};