思路：我们只要check一遍每个长度为k的区间就好啦，对于一个区间来说的最优值显然是中位数，我们显然要动态求

第k大，所以需要一个二叉搜索树，用treap就好啦。

#include
     
      #define LL long long#define fi first#define se second#define mk make_pair#define pii pair
      
       #define piii pair
       
         >using namespace std;const int N = 2e5 + 10;const int M = 10 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-6;int n, k, a[N];struct node {    node* ch[2];    int key, fix, sz, cnt;    LL sum;    void update() {        sz = ch[0]->sz + ch[1]->sz + cnt;        sum = ch[0]->sum + ch[1]->sum + 1ll * cnt * key;    }};typedef node* P_node;struct Treap {    node base[N], nil;    P_node root, null, len;    Treap() {        root = null = &nil;        null->key = null->fix = 1e9;        null->sz = null->cnt = null->sum = 0;        null->ch[0] = null->ch[1] = null;        len = base;    }    P_node newnode(int tkey) {        len->key = tkey;        len->fix = rand();        len->ch[0] = len->ch[1] = null;        len->sz = len->cnt = 1;        len->sum = tkey;        return len++;    }    void rot(P_node &p, int d) {        P_node k = p->ch[d ^ 1];        p->ch[d ^ 1] = k->ch[d];        k->ch[d] = p;        p->update();        k->update();        p = k;    }    void _Insert(P_node &p, int tkey) {        if(p == null) {            p = newnode(tkey);        } else if(p->key == tkey) {            p->cnt++;        } else {            int d = tkey > p->key;            _Insert(p->ch[d], tkey);            if(p->ch[d]->fix > p->fix) {                rot(p, d ^ 1);            }        }        p->update();    }    void _Delete(P_node &p, int tkey) {        if(p == null) return;        if(p->key == tkey) {            if(p->cnt > 1) p->cnt--;            else if(p->ch[0] == null) p = p->ch[1];            else if(p->ch[1] == null) p = p->ch[0];            else {                int d = p->ch[0]->fix > p->ch[1]->fix;                rot(p, d);                _Delete(p->ch[d], tkey);            }        } else {            _Delete(p->ch[tkey > p->key], tkey);        }        p->update();    }    int _Kth(P_node p, int k) {        if(p == null || k < 1 || k > p->sz) return 0;        if(k < p->ch[0]->sz + 1) return _Kth(p->ch[0], k);        if(k > p->ch[0]->sz + p->cnt) return _Kth(p->ch[1], k - p->ch[0]->sz - p->cnt);        return p->key;    }    int _Rank(P_node p, int tkey, int res) {        if(p == null) return -1;        if(p->key == tkey) return p->ch[0]->sz + res + 1;        if(tkey < p->key) return _Rank(p->ch[0], tkey, res);        return _Rank(p->ch[1], tkey, res + p->ch[0]->sz + p->cnt);    }    int _Pred(P_node p, int tkey){        if(p == null) return -1e9;        if(tkey <= p->key) return _Pred(p->ch[0], tkey);        return max(p->key, _Pred(p->ch[1], tkey));    }    int _Succ(P_node p, int tkey){        if(p == null) return 1e9;        if(tkey >= p->key) return _Succ(p->ch[1], tkey);        return min(p->key, _Succ(p->ch[0], tkey));    }    void _Print(P_node p){        if(p == null) return;        _Print(p -> ch[0]);        for(int i = 1; i <= p->cnt; i++) printf("%d ",p->key);        _Print(p->ch[1]);    }    LL _Query(P_node p, int tkey) {        if(p == null) return 0;        if(p->key == tkey) {            return 1ll * tkey * p->ch[0]->sz - p->ch[0]->sum + p->ch[1]->sum - 1ll * tkey * p->ch[1]->sz;        } else if(p->key < tkey) {            return 1ll * tkey * (p->ch[0]->sz + p->cnt) - (p->ch[0]->sum + 1ll * p->cnt * p->key) + _Query(p->ch[1], tkey);        } else {            return (p->ch[1]->sum + 1ll * p->cnt * p->key) - 1ll * tkey * (p->ch[1]->sz + p->cnt) + _Query(p->ch[0], tkey);        }    }    void Insert(int tkey){ _Insert(root,tkey); }    void Delete(int tkey){ _Delete(root,tkey); }    int Kth(int k){ return _Kth(root,k); }    int Rank(int tkey){ return _Rank(root,tkey,0); }    int Pred(int tkey){ return _Pred(root,tkey); }    int Succ(int tkey){ return _Succ(root,tkey); }    void Print(){ _Print(root); printf("\n"); }    LL Query(int tkey) { return _Query(root, tkey); }}tp;int main() {    scanf("%d%d", &n, &k);    for(int i = 1; i <= n; i++) {        scanf("%d", &a[i]);    }    for(int i = 1; i <= k; i++) {        tp.Insert(a[i]);    }    int l = 1, r = k, mid = k / 2;    if(k & 1) mid++;    LL ans = INF;    while(r <= n) {        int num = tp.Kth(mid);        ans = min(ans, tp.Query(num));        tp.Delete(a[l++]);        tp.Insert(a[++r]);    }    printf("%lld\n", ans);    return 0;}/*5 53 9 2 3 1*/