水一发。
本来可以直接拿主席树找中位数的，但是因为main上只有32MB，所以只好写了个splay。感觉现在是爱上指针了。然后kth的时候少打个等号又wa又re好爽。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long dint;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (long long int)
const int maxn = 100009;
#define nsz(p) ((p)?(p->sz):0)
#define sof(p) ((p)?(p->s):0)
struct splay_node {
int v, sz;
dint s;
splay_node *ls, *rs, *pt;
inline void init(int v0) {
v = v0;
sz = 1;
s = v0;
pt = ls = rs = 0;
}
inline void update() {
s = v;
sz = 1;
if (ls) {
s += ls-> s;
sz += ls-> sz;
}
if (rs) {
s += rs-> s;
sz += rs-> sz;
}
}
};
struct splay_tree {
splay_node *cr, *sp, slst[maxn];
inline splay_tree() {
cr = 0;
sp = slst;
}
inline void rot(splay_node* q) {
splay_node *p = q-> pt;
if (p-> pt) {
if (p-> pt-> ls == p)
p-> pt-> ls = q;
else
p-> pt-> rs = q;
}
q-> pt = p-> pt;
p-> pt = q;
if (q == p-> ls) {
if (q-> rs)
q-> rs-> pt = p;
p-> ls = q-> rs;
q-> rs = p;
}
else {
if (q-> ls)
q-> ls-> pt = p;
p-> rs = q-> ls;
q-> ls = p;
}
p-> update();
q-> update();
}
void splay(splay_node* q) {
while (q-> pt) {
splay_node *p = q-> pt;
if (!p-> pt)
rot(q);
else if ((p == p-> pt-> ls) == (q == p-> ls))
rot(p), rot(q);
else
rot(q), rot(q);
}
cr = q;
}
splay_node* kth(splay_node* p, int k) {
while (p)
if (nsz(p-> ls) + 1 == k)
break;
else if (nsz(p-> ls) >= k)
p = p-> ls;
else
k -= nsz(p-> ls) + 1, p = p-> rs;
return p;
}
void ins(int v) {
splay_node *x = sp ++;
x-> init(v);
if (!cr)
cr = x;
else {
splay_node *p = cr;
while (p)
if (v < p-> v) {
if (!p-> ls) {
p-> ls = x;
x-> pt = p;
break;
}
else
p = p-> ls;
}
else {
if (!p-> rs) {
p-> rs = x;
x-> pt = p;
break;
}
else
p = p-> rs;
}
splay(x);
}
}
void ers(int v) {
splay_node *p = cr;
while (p)
if (p-> v == v)
break;
else if (v < p-> v)
p = p-> ls;
else
p = p-> rs;
splay(p);
if (!p-> rs) {
if (p-> ls)
p-> ls-> pt = 0;
cr = p-> ls;
}
else {
p-> rs-> pt = 0;
splay_node* q = kth(p-> rs, 1);
splay(q);
q-> ls = p-> ls;
if (p-> ls)
p-> ls-> pt = q;
q-> update();
cr = q;
}
}
dint ans(int k) {
splay_node *p = kth(cr, (k + 1) >> 1);
splay(p);
if (k & 1)
return sof(p-> rs) - sof(p-> ls);
else
return sof(p-> rs) - p-> v - sof(p-> ls);
}
inline int midv() {
return cr-> v;
}
};
int n, k, a[maxn];
int p0, v0;
dint ans;
splay_tree t;
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++ i)
scanf("%d", a + i);
for (int i = 0; i < k; ++ i)
t. ins(a[i]);
ans = t. ans(k);
p0 = 0;
v0 = t. midv();
for (int i = k; i < n; ++ i) {
t. ers(a[i - k]);
t. ins(a[i]);
dint vn = t. ans(k);
if (vn < ans) {
ans = vn;
p0 = i - k + 1;
v0 = t. midv();
}
}
printf(lld "\n", ans);
/*for (int i = p0; i < p0 + k; ++ i)
a[i] = v0;
for (int i = 0; i < n; ++ i)
printf("%d\n", a[i]);*/
}