思路：我们只要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 + ;
const int M = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int n, k, a[N]; struct node {
node* ch[];
int key, fix, sz, cnt;
LL sum; void update() {
sz = ch[]->sz + ch[]->sz + cnt;
sum = ch[]->sum + ch[]->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 = ;
null->ch[] = null->ch[] = null;
len = base;
} P_node newnode(int tkey) {
len->key = tkey;
len->fix = rand();
len->ch[] = len->ch[] = null;
len->sz = len->cnt = ;
len->sum = tkey;
return len++;
} void rot(P_node &p, int d) {
P_node k = p->ch[d ^ ];
p->ch[d ^ ] = 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 ^ );
}
}
p->update();
} void _Delete(P_node &p, int tkey) {
if(p == null) return;
if(p->key == tkey) {
if(p->cnt > ) p->cnt--;
else if(p->ch[] == null) p = p->ch[];
else if(p->ch[] == null) p = p->ch[];
else {
int d = p->ch[]->fix > p->ch[]->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 < || k > p->sz) return ;
if(k < p->ch[]->sz + ) return _Kth(p->ch[], k);
if(k > p->ch[]->sz + p->cnt) return _Kth(p->ch[], k - p->ch[]->sz - p->cnt);
return p->key;
} int _Rank(P_node p, int tkey, int res) {
if(p == null) return -;
if(p->key == tkey) return p->ch[]->sz + res + ;
if(tkey < p->key) return _Rank(p->ch[], tkey, res);
return _Rank(p->ch[], tkey, res + p->ch[]->sz + p->cnt);
} int _Pred(P_node p, int tkey){
if(p == null) return -1e9;
if(tkey <= p->key) return _Pred(p->ch[], tkey);
return max(p->key, _Pred(p->ch[], tkey));
} int _Succ(P_node p, int tkey){
if(p == null) return 1e9;
if(tkey >= p->key) return _Succ(p->ch[], tkey);
return min(p->key, _Succ(p->ch[], tkey));
} void _Print(P_node p){
if(p == null) return;
_Print(p -> ch[]);
for(int i = ; i <= p->cnt; i++) printf("%d ",p->key);
_Print(p->ch[]);
} LL _Query(P_node p, int tkey) {
if(p == null) return ; if(p->key == tkey) {
return 1ll * tkey * p->ch[]->sz - p->ch[]->sum + p->ch[]->sum - 1ll * tkey * p->ch[]->sz;
} else if(p->key < tkey) {
return 1ll * tkey * (p->ch[]->sz + p->cnt) - (p->ch[]->sum + 1ll * p->cnt * p->key) + _Query(p->ch[], tkey);
} else {
return (p->ch[]->sum + 1ll * p->cnt * p->key) - 1ll * tkey * (p->ch[]->sz + p->cnt) + _Query(p->ch[], 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,); }
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 = ; i <= n; i++) {
scanf("%d", &a[i]);
} for(int i = ; i <= k; i++) {
tp.Insert(a[i]);
} int l = , r = k, mid = k / ;
if(k & ) 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 ;
}
/*
5 5
3 9 2 3 1
*/