C++ 2 methods (Segment Tree && heaps)
The core of this problem is:\n\n> How to find the sum of the smallest/biggest 1~k th numbers in an array?\n\nSegment tree can do this in O(nlogn) time.\n\nWe ca
The core of this problem is:\n\n> How to find the sum of the smallest/biggest 1~k th numbers in an array?\n\nSegment tree can do this in `O(nlogn)` time.\n\nWe can keep a segment tree which stores the information about: "For a given value x, how many x are there in the array?".\n\nFor example the current array is `[3,1,10,5,5]`, then the tree node for value `5` will have a `cnt = 2`. To further speed up the code, we can keep an extra `sum` in the tree node. \n\nTo be more precise, if a tree node tells about the information of `[l,r]`, then the `cnt` and `sum` implies:\n`cnt` is the number of elements `x`, where `l <= x <= r`.\n`sum` is the **sum of elements** `x`, where `l <= x <= r`.\n\nNow we can easily query about the sum of first `k-th` smallest and biggest elements. \n\n<hr>\n\n```cpp\n#define maxn (100005<<2)\n#define ll long long\nstruct node {\n    int cnt;\n    ll sum;\n} tr[maxn];\n\nvoid push_up(int cur) {\n    tr[cur].cnt = tr[cur<<1].cnt + tr[cur<<1|1].cnt;\n    tr[cur].sum = tr[cur<<1].sum + tr[cur<<1|1].sum;\n}\n\nvoid update(int cur, int l, int r, int p, int x) {\n    if (l == r) {\n        tr[cur].sum += (ll)(x * p);\n        tr[cur].cnt += x;\n        return;\n    }\n    int mid = (l+r) >> 1;\n    if (p <= mid) update(cur<<1, l, mid, p, x);\n    else update(cur<<1|1, mid+1, r, p, x);\n    push_up(cur);\n}\n\n// return the sum of the smallest 1~kth numbers\nll query_small(int cur, int l, int r, int k) {\n    if (k <= 0) return 0;\n    if (tr[cur].cnt <= k) return tr[cur].sum;\n    if (l == r) {\n        return (ll)(l) * (ll)(k);  // for example [5,5,5], k = 1, only return 5, not 15\n    }\n    int mid = (l+r) >> 1;\n    ll res = 0;\n    res += query_small(cur<<1, l, mid, k);\n    res += query_small(cur<<1|1, mid+1, r, k-tr[cur<<1].cnt);\n    return res;\n}\n\n// return the sum of the biggest 1~kth numbers\nll query_big(int cur, int l, int r, int k) {\n    if (k <= 0) return 0;\n    if (tr[cur].cnt <= k) return tr[cur].sum;\n    if (l == r) {\n        return (ll)(l) * (ll)(k);  // for example [5,5,5], k = 1, only return 5, not 15\n    }\n    int mid = (l+r) >> 1;\n    ll res = 0;\n    res += query_big(cur<<1, l, mid, k-tr[cur<<1|1].cnt);\n    res += query_big(cur<<1|1, mid+1, r, k);\n    return res;\n}\n\nclass MKAverage {\npublic:\n    int m,k;\n    vector<int> vec;\n    ll sum = 0;\n    int de;\n    \n    MKAverage(int m, int k) {\n        this->m = m;\n        this->k = k;\n        de = m-2*k;\n        memset(tr, 0, sizeof(tr));\n    }\n            \n    void addElement(int num) {\n        vec.push_back(num);\n        sum += (ll)(num);\n        int n = vec.size();\n        update(1, 1, 1e5, num, 1);\n        \n        if (n > m) {\n            int cur = vec[n-m-1];\n            sum -= cur;\n            update(1, 1, 1e5, cur, -1);\n        }\n    }\n    \n    int calculateMKAverage() {\n        if (vec.size() < m) return -1;\n        ll res = query_small(1, 1, 1e5, k) + query_big(1, 1, 1e5, k);\n        return (sum - res) / de;\n    }\n};\n```\n\n<hr>\n\nSome sidenotes:\n\nSegment tree can also solve the following problems:\n\n1. Find the `k` th smallest element in an array.\n2. Find the number of pairs `(i,j)` such that `arr[i] > arr[j]`.\n3. Find the maximum **unique** element in a sliding window. (https://codeforces.com/problemset/problem/69/E).\n\nPlease see my blog (Chinese only) for Segment tree: https://tom0727.gitee.io/post/035-%E6%9D%83%E5%80%BC%E7%BA%BF%E6%AE%B5%E6%A0%91/\n\nIf you are interested, you can also learn about **Persistent Segment Tree**, which can solve problems like:\n\n1. Find the `k` th smallest element in **any segment** of an array.\n2. Answer queries about **any history version** of an array.\n3. Find the **LCM** of any segments of an array. (https://codeforces.com/problemset/problem/1422/F)\n4. In a **tree (n vertices, n-1 edges, connected graph)**, where every edge has a weight, find the `k`th smallest weight in the shortest path between `u,v`.\n\nPlease see my blog (Chinese only) for Persistent Segment tree: https://tom0727.gitee.io/post/036-%E4%B8%BB%E5%B8%AD%E6%A0%91/\n\n\n\n<hr>\n\nThe second method is using 3 heaps. Others have explained that solution well enough. I will only post my code here:\n\n```cpp\nclass MKAverage {\npublic:\n    #define ll long long\n    int m,k;\n    vector<int> vec;\n    multiset<int> small, mid, big;\n    ll sum = 0;\n    int de;\n    \n    MKAverage(int m, int k) {\n        this->m = m;\n        this->k = k;\n        de = m-2*k;\n    }\n\t\n    void addElement(int num) {\n        vec.push_back(num);\n        sum += (ll)(num);\n        mid.insert(num);\n        int n = vec.size();\n        if (n < m) return;\n        \n        if (n == m) {\n            for (int i = 0; i < k; i++) {\n                auto itr = prev(mid.end());\n                int cur = *itr;\n                big.insert(cur);\n                mid.erase(itr);\n                sum -= cur;\n            }\n            for (int i = 0; i < k; i++) {\n                auto itr = mid.begin();\n                int cur = *itr;\n                small.insert(cur);\n                mid.erase(itr);\n                sum -= cur;\n            }\n            return;\n        }\n        \n        \n        if (n > m) {\n            int cur = vec[n-m-1];\n            if (small.count(cur)) {\n                small.erase(small.find(cur));\n            } else if (big.count(cur)) {\n                big.erase(big.find(cur));\n            } else if (mid.count(cur)) {\n                sum -= cur;\n                mid.erase(mid.find(cur));\n            }\n        }\n        \n        if (small.size() < k) {\n            auto itr = mid.begin();\n            int cur = *itr;\n            sum -= cur;\n            small.insert(cur);\n            mid.erase(itr);\n        }\n        if (big.size() < k) {\n            auto itr = prev(mid.end());\n            int cur = *itr;\n            sum -= cur;\n            big.insert(cur);\n            mid.erase(itr);\n        }\n        \n        while (*prev(small.end()) > *mid.begin()) {\n            auto itr1 = prev(small.end());\n            auto itr2 = mid.begin();\n            int cur1 = *itr1, cur2 = *itr2;\n            small.erase(itr1); mid.erase(itr2);\n            small.insert(cur2); mid.insert(cur1);\n            sum -= cur2, sum += cur1;\n        }\n        \n        while (*big.begin() < *prev(mid.end())) {\n            auto itr1 = big.begin();\n            auto itr2 = prev(mid.end());\n            int cur1 = *itr1, cur2 = *itr2;\n            big.erase(itr1); mid.erase(itr2);\n            big.insert(cur2); mid.insert(cur1);\n            sum -= cur2, sum += cur1;\n        }\n    }\n    \n    int calculateMKAverage() {\n        if (vec.size() < m) return -1;\n        return sum / de;\n    }\n};\n```\n
[]