#include<bits/stdc++.h> #define int long long using namespace std; int n,k,x; const int N=1e6+7; int a[N]; int s1[N],s2[N],sum1[N],sum2[N]; int t1[N],t2[N]; void pushup(int x) { t1[x]=min(t1[x*2],t1[x*2+1]); t2[x]=min(t2[x*2],t2[x*2+1]); } void build(int x,int l,int r) { if(l==r) { t1[x]=sum1[l]; t2[x]=sum2[l]; return ; } int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); pushup(x); return ; } int query1(int x,int l,int r,int L,int R) { if(l>=L&&r<=R) return t1[x]; int mid=(l+r)/2; int minn=1e18; if(L<=mid) minn=min(minn,query1(x*2,l,mid,L,R)); if(R>mid) minn=min(minn,query1(x*2+1,mid+1,r,L,R)); return minn; } int query2(int x,int l,int r,int L,int R) { if(l>=L&&r<=R) return t2[x]; int mid=(l+r)/2; int minn=1e18; if(L<=mid) minn=min(minn,query2(x*2,l,mid,L,R)); if(R>mid) minn=min(minn,query2(x*2+1,mid+1,r,L,R)); return minn; } int maxx1=0,maxx2=0; signed main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); memset(t1,0x3f,sizeof(t1)); memset(t2,0x3f,sizeof(t2)); cin>>n>>k>>x; if(x<0) { x=-x; k=n-k; } for(int i=1;i<=n;i++) { cin>>a[i]; s1[i]=a[i]+x; s2[i]=a[i]-x; sum1[i]=sum1[i-1]+s1[i]; sum2[i]=sum2[i-1]+s2[i]; } build(1,1,n); for(int i=1;i<=n;i++) { int val=query1(1,1,n,max((int)1,i-k),i); if(i-k<=0) val=min(val,(int)0); maxx1=max(maxx1,(int)sum1[i]-val); } maxx2=sum2[k]; for(int i=k+1;i<=n;i++) { int val=query2(1,1,n,1,i-k); val=min(val,(int)0); maxx2=max(maxx2,(int)sum2[i]-val); } int ans; ans=max(maxx1,maxx2+2*k*x); cout<<ans; return 0; } /* 注意到，当 x<0 时，可以直接将 x=-x ,k=n-k 现在可以正常做了。 发现对于每一段区间，若选择它，则： S=sum+min(k,r-l+1)*x-max(0,r-l+1-k)*x 而这个 min/max 的取值是取决于 k 与区间长度的。 所以我们可以分成 2 部分考虑： 1.r-l+1>k 可得：S=sum+k*x-(len-k)*x=sum+(2*k-len)*x=sum+2kx-len*x 2.r-l+1<=k 可得：S=sum+len*x 我们可以发现，2kx是一个常数可以忽略，所以我们可以把序列分成2段处理。 首先，我们将序列全体 +x，然后算长度小于 k 的最大和 然后再将序列全体 -x，算长度大于 k 的最大序列和 最后将 -x 的答案 +2kx，比较大小即可 整 2 棵线段树维护前缀和，然后直接找区间最小值即可 6 2 7 3 -8 2 -19 7 -14 */