LG-P2263

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 500010;

int n;
struct Node {
    int x, id;

    bool operator< (const Node &t) const {
        return x < t.x;
    }
} b[N];
int k, p;
int a[N], c[N];
int tr1[N], tr2[N], val[N];

inline int lowbit(int x)
{
    return x & -x;
}

void add1(int x, int y)
{
    for ( ; x <= p; x += lowbit(x)) tr1[x] += y;
}

void add2(int x, int y)
{
    for ( ; x <= p; x += lowbit(x)) tr2[x] += y;
}

inline int query1(int x)
{
    int sum = 0;
    for (; x; x -= lowbit(x))
        sum += tr1[x];
    return sum;
}
inline int query2(int x)
{
    int sum = 0;
    for (; x; x -= lowbit(x))
        sum += tr2[x];
    return sum;
}

inline int find(int x){ //二分配合树状数组查找中位数
    int l = 0, r = p;
    while (l < r){
        int mid = l + r >> 1;
        if (query1(mid) >= x) r = mid;
        else l = mid + 1;
    }   
    return l;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i ++ )  cin >> a[i], b[i].x = a[i], b[i].id = i;

    sort(b + 1, b + 1 + n);
    b[0].x = b[1].x - 1;

    for (int i = 1; i <= n; i ++ )  c[b[i].id] = b[i].x == b[i - 1].x ? p : ++ p, val[p] = b[i].x;

    for (int i = 1; i <= k; i ++ )  add1(c[i], 1), add2(c[i], a[i]);

    int ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = k + 1; i <= n + 1; i ++ )
    {
        int tmp = find(k + 1 >> 1);
        int mid = val[tmp];

        ans = min(ans, query1(tmp - 1) * mid - query2(tmp - 1) + query2(p) - query2(tmp) - (query1(p) - query1(tmp)) * mid);
        if (i == n + 1) break;

        add1(c[i - k], -1), add1(c[i], 1);
        add2(c[i - k], -a[i - k]), add2(c[i], a[i]);
    }

    cout << ans;
}