根据贪心策略，应当选择 \(k\) 个最小的负数改为正数，或选择 \(k\) 个最大的正数改为负数，才可能使答案最大。那么可以先把数按正负分开，并确定每个数在同符号数中的排名。建立权值线段树，记录每个数出现的次数、单个数大小、总贡献和，查询时类似线段树二分，如果数值较大的区间不够用，就往数值较小的区间递归，否则在其内部递归。循环时分别维护当前的正数和、负数和。时间复杂度 \(O(n\log n)\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 200010
#define int long long
using namespace std;
struct node{int val,siz,v;
};
struct T{node t[N*4];void pushup(int u){t[u].val=t[u<<1].val+t[u<<1|1].val;t[u].siz=t[u<<1].siz+t[u<<1|1].siz;}void upd(int u,int l,int r,int p,int v,int ki){if(l==r){t[u].v=v;t[u].siz+=ki;t[u].val=t[u].siz*v;return;}int mid=(l+r)>>1;if(p<=mid)upd(u<<1,l,mid,p,v,ki);if(p>mid)upd(u<<1|1,mid+1,r,p,v,ki);pushup(u);}int que(int u,int l,int r,int nw){if(l>r||nw==0)return 0;// cout<<l<<' '<<r<<endl;if(l==r)return t[u].v*min(t[u].siz,nw);int mid=(l+r)>>1;if(t[u<<1|1].siz>=nw)return que(u<<1|1,mid+1,r,nw);else return t[u<<1|1].val+que(u<<1,l,mid,nw-t[u<<1|1].siz);}
}tp,tn;
struct L{int val,ki,id;
}a[N];
int n,len,pm,nm,k,pa[N],na[N],sp,sn,ans;
void modify(int i,int val){if(a[i].ki==-1)tn.upd(1,1,nm,a[i].id,a[i].val,val);if(a[i].ki==1)tp.upd(1,1,pm,a[i].id,a[i].val,val);
}
signed main(){cin>>n>>len;for(int i=1;i<=n;i++){cin>>a[i].val;if(a[i].val<0)a[i].val*=-1,a[i].ki=-1,na[++nm]=a[i].val;else if(a[i].val>0)a[i].ki=1,pa[++pm]=a[i].val;}cin>>k;sort(pa+1,pa+pm+1);sort(na+1,na+nm+1);nm=unique(na+1,na+nm+1)-na-1;pm=unique(pa+1,pa+pm+1)-pa-1;for(int i=1;i<=n;i++){if(a[i].ki==-1)a[i].id=lower_bound(na+1,na+nm+1,a[i].val)-na;if(a[i].ki==1)a[i].id=lower_bound(pa+1,pa+pm+1,a[i].val)-pa;// cout<<i<<' '<<a[i].id<<endl;}for(int i=1;i<len;i++){modify(i,1);if(a[i].ki==-1)sn+=a[i].val;else sp+=a[i].val;}for(int i=1;i+len-1<=n;i++){int j=i+len-1;modify(j,1);if(a[j].ki==-1)sn+=a[j].val;else sp+=a[j].val;// cout<<1<<endl;ans=max(ans,abs(sn+tp.que(1,1,pm,k)-(sp-tp.que(1,1,pm,k))));ans=max(ans,abs(sp+tn.que(1,1,nm,k)-(sn-tn.que(1,1,nm,k))));// cout<<i<<' '<<j<<' '<<sn<<' '<<sp<<' '<<abs(sn+tp.que(1,1,pm,k)-(sp-tp.que(1,1,pm,k)))<<' '<<abs(sp+tn.que(1,1,nm,k)-(sn-tn.que(1,1,nm,k)))<<endl;modify(i,-1);if(a[i].ki==-1)sn-=a[i].val;else sp-=a[i].val;}cout<<ans;return 0;
}