[C++]Fenwick Tree Solution.
The idea for the problem is to maintain a data structure so that it can list the first k numbers\' sum and last k numbers\' sum quickly. It will also have the c
The idea for the problem is to maintain a data structure so that it can list the first k numbers\' sum and last k numbers\' sum quickly. It will also have the capability of counting how many elements there are between specific range of the values. The data structure has the aformentioned abilities is a Fenwick Tree. You can have the implementation of a segment tree as well. But it will overcomplicate the issue.\n\nHow do we find the sum of first k elements? Essentially, whenever a new element flies in, we have a sliding window to window out an element that is out of the last m elements. We can use -1 and -value on the Fenwick tree to undo its effect. \n\nNow, we want to find the first k elements\' sum. We can use binary search to find the value such that the sum of the occurence of values less than a given value x is less than k, and we will have to find the first spot such property violated.\n\nWe just need to do some simple math to figure out what exactly the sum of the first k elements will be given the value of the violator and the value of the sum before the violator. And we will get the first k elements\' sum.\n\nFor the last k elements, it works the same.\n\nMy code is written in cLay, a transpiler written by LayCurse. For accessing it, you can either visit his yukicoder page or you can visit the link here: [LayCurse\'s Blog](http://rsujskf.s602.xrea.com/)\n\n```\n#define main dummy_main\n{}\n#undef main\n\nconst int MN = 1d5+10;\nclass MKAverage {\npublic:\n    int m, k, size, a[MN];\n    fenwick<ll> tr[2];\n\n    MKAverage(int m, int k) {\n        this->m = m;\n        this->k = k;\n        this->size = 0;\n        dummy_main();\n        rep(i,0,2){\n            tr[i].walloc(MN);\n            tr[i].init(MN);\n        }\n    }\n    \n    void addElement(int num) {\n        int & x = this->size;\n        if( x >= m){\n            tr[0].add(a[x-m], -1);\n            tr[1].add(a[x-m], -a[x-m]);\n        }\n        a[x] = num;\n        tr[0].add(num, 1);\n        tr[1].add(num, num); \n        ++x; \n    }\n    \n    int calculateMKAverage() {\n        // tr[0].range(0, x);\n        // tr[0].range(x,1d5+2);\n        if(size < m) return -1;\n        auto u =bsearch_max[int, x, 0, 1d5+2] (tr[0].range(0,x) <= k);\n        u = max(u-2,0);\n        while(tr[0].range(0,u) <= k) ++u;\n        --u;\n        auto v = tr[0].range(0,u);\n        auto vv = k-v;\n        auto lowex = vv*(u+1) + tr[1].range(0,u);\n        //part one\n\n        auto uu = bsearch_min[int, x, 0, 1d5+2] (tr[0].range(x,1d5+2) <= k);\n        uu = min(uu+2,1d5+2);\n        while(tr[0].range(uu, 1d5+2) <= k) --uu;\n        ++uu;\n        auto vvv = tr[0].range(uu, 1d5+2);\n        auto vx = k-vvv;\n        auto upperx = vx * (uu-1)+tr[1].range(uu, 1d5+2);\n        auto whole = tr[1].range(0,1d5+2);\n        return (whole-upperx-lowex)/(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\n\n// void main(){\n\n//     MKAverage mk(3,1);\n//     mk.addElement(3);\n//     mk.addElement(1);\n//     wt( mk.calculateMKAverage());\n//     mk.addElement(10);\n//     wt(mk.calculateMKAverage());\n//     mk.addElement(5);\n//     mk.addElement(5);\n//     mk.addElement(5);\n//     __asm int 3;\n//     wt(mk.calculateMKAverage());\n// }\n```
[]