思路：我们只要check一遍每个长度为k的区间就好啦，对于一个区间来说的最优值显然是中位数，我们显然要动态求
第k大，所以需要一个二叉搜索树，用treap就好啦。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define pii pair<int,int> #define piii pair<int, pair<int,int> >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 5 3 9 2 3 1 */