Sliding Cost

#include <bits/stdc++.h>
using namespace std;
void add(int i, vector<long long> &a, long long d) {
    i++;
    int n=a.size();
    while(i<n) {
        a[i]+=d;
        i+=i&-i;
    }
}
long long sum(int i, vector<long long> &a) {
    i++;
    long long ans=0;
    while(i) {
        ans+=a[i];
        i-=i&-i;
    }
    return ans;
}
int find(vector<long long> &a, int target) {
    int low=0, high=a.size()-2, mid;
    while(low<high) {
        mid=low+(high-low)/2;
        if(sum(mid, a)<target) {
            low=mid+1;
        } else {
            high=mid;
        }
    }
    return low;
}
void solve() {
    int n, k, i, index;
    long long cost;
    cin>>n>>k;
    vector<long long> givenOrder(n), active(n+1, 0), cumlativeF(n+1, 0);
    vector<pair<long long, int>> numToIndex(n);    
    for(i=0; i<n; i++) {
        cin>>givenOrder[i];
        numToIndex[i].first=givenOrder[i];        
        //storing the initial index
        numToIndex[i].second=i;
    }
    //order for BIT
    sort(numToIndex.begin(), numToIndex.end());
    for(i=0; i<n; i++) {
        givenOrder[numToIndex[i].second]=i;
        //givenOrder[i] = index of element in BIT
    }
    for(i=0; i<n; i++) {
        //add givenOrder[i] to window
        add(givenOrder[i], cumlativeF, 1);
        add(givenOrder[i], active, numToIndex[givenOrder[i]].first);
        if(i>=k-1) {
            //find the index of median in the cumlativeF array
            index=find(cumlativeF, (k+1)/2);
           //make every element equal to median for minimum cost
            cost=sum(n-1, active)-2*sum(index, active)+(k%2?numToIndex[index].first:0);            
            cout<<cost<<" ";            
            //removing givenOrder[i-k+1] for future windows
            add(givenOrder[i-k+1], cumlativeF, -1);
            add(givenOrder[i-k+1], active, -1*numToIndex[givenOrder[i-k+1]].first);
        }
    }
    cout<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

void solve() { int n , k; cin >> n >> k;

int a[n];
for(int i = 0; i < n; i++) {
    cin >> a[i];
}

multiset<int> smaller , bigger;

int i = 0 , j = 0;
int sumSmaller = 0 , sumBigger = 0;

while(j < n) {
    if(smaller.size() == bigger.size()) {
       bigger.insert(a[j]);
       int ele = *bigger.begin();
       bigger.erase(bigger.begin());
       smaller.insert(ele);
       sumSmaller += ele;
       sumBigger -= ele;
       sumBigger += a[j];
    }
    else {
       sumSmaller += a[j];
       smaller.insert(a[j]);
       int ele = *smaller.rbegin();
       sumSmaller -= *smaller.rbegin();
       smaller.erase(--smaller.end());
       bigger.insert(ele);
       sumBigger += ele;
    }

    if(j - i + 1 < k) {
       j++;
    }
    else if(j - i + 1 == k) {
       int median = *smaller.rbegin();
       int ans = 0;
       ans += smaller.size() * median - sumSmaller;
       ans += sumBigger - bigger.size() * median;

       cout << ans << " ";

       int temp = a[i];
       if(smaller.find(temp) != smaller.end()) {
         if(smaller.size() == bigger.size()) {
          int eles = *bigger.begin();
          bigger.erase(bigger.begin());
          smaller.insert(eles);
          sumSmaller += eles;
          sumBigger -= eles;
         }
         sumSmaller -= temp;
         smaller.erase(smaller.find(temp));
       }
       else {
         if(smaller.size() != bigger.size()) {
          int eles = *smaller.rbegin();
          smaller.erase(--smaller.end());
          bigger.insert(eles);
          sumSmaller -= eles;
          sumBigger += eles;
         }
         sumBigger -= temp;
         bigger.erase(bigger.find(temp));
       }
       i++;
       j++;
    }
}

}

  ll n,k;
  cin>>n>>k;
  vl aa(n);
  fo(i,n){
    cin>>aa[i];
  }
  prq_mx<pl> l;
  prq_mn<pl> r;
  ll mid=(k+1)/2;
  ll c=0;
  ll lsum=0,rsum=0;
  fo(i,n){
    while(Sz(l) && l.top().se<=(i-k))l.pop();
    while(Sz(r) && r.top().se<=(i-k))r.pop();
    if(c<mid){
      r.push({aa[i],i});
      rsum+=aa[i];
      l.push(r.top());
      lsum+=r.top().fi;
      rsum-=r.top().fi;
      r.pop();
      c++;
    }else{
      l.push({aa[i],i});
      lsum+=aa[i];
      r.push(l.top());
      rsum+=l.top().fi;
      lsum-=l.top().fi;
      l.pop();
    }
    if(i-k+1<0)continue;
    ll med=l.top().fi;
    ll ans1=(mid*med)-lsum + rsum-((k-mid)*med );
    cout<<ans1<<" ";
    if(aa[i-k+1]<=l.top().fi){
      lsum-=aa[i-k+1];
      c--;
    }else rsum-=aa[i-k+1];
  }
  cout<<nline;