记录编号	579665	评测结果	AAAAAAAAAA
题目名称	简短的题目	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.811 s
提交时间	2023-07-11 10:02:33	内存使用	64.21 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int N=100000+5;
int n,m,lgn,L,R;
ll a[N],sum[N];
ll mx[20][N],mxi[20][N];
ll mn[20][N],mni[20][N];
inline ll read(){
    ll ans=0,sgn=1;char ch=getchar();
    while(!isdigit(ch)){
        if (ch=='-')sgn=-1;
        ch=getchar();
    }
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans*sgn;
}
inline void write(ll x){
    if (x<0)putchar('-'),x=-x;
    if (x>9)write(x/10);
    putchar(x%10+'0');
}
void prework(){
    for (int i=0;i<lgn;i++){
        for (int j=0;j+(1<<i)<=n;j++){
            if (mx[i][j]<=mx[i][j+(1<<i)]){
                mx[i+1][j]=mx[i][j+(1<<i)];
                mxi[i+1][j]=mxi[i][j+(1<<i)];
            }else{
                mx[i+1][j]=mx[i][j];
                mxi[i+1][j]=mxi[i][j];
            }
        }
    }
    for (int i=0;i<lgn;i++){
        for (int j=0;j+(1<<i)<=n;j++){
            if (mn[i][j]>=mn[i][j+(1<<i)]){
                mn[i+1][j]=mn[i][j+(1<<i)];
                mni[i+1][j]=mni[i][j+(1<<i)];
            }else{
                mn[i+1][j]=mn[i][j];
                mni[i+1][j]=mni[i][j];
            }
        }
    }
}
int getmxi(int l,int r){
    int k=1.0*log(r-l+1)/log(2);
    return (mx[k][l]>mx[k][r-(1<<k)+1])?mxi[k][l]:mxi[k][r-(1<<k)+1];
}
int getmni(int l,int r){
    int k=1.0*log(r-l+1)/log(2);
    return (mn[k][l]<mn[k][r-(1<<k)+1])?mni[k][l]:mni[k][r-(1<<k)+1];
}
ll tag[4*N];
void update(int pt,int l,int r,int x,int y,ll w){
    if (x<=l&&r<=y){
        tag[pt]=max(tag[pt],w);return ;
    }int mid=(l+r)/2;
    if (x<=mid)update(pt*2,l,mid,x,y,w);
    if (mid+1<=y)update(pt*2+1,mid+1,r,x,y,w);
}
void calcR(int i){
    int suf=getmxi(i+L-1,min(i+R-1,n));
    int pre=getmni(max(suf-R,0),i-1);
    update(1,1,n,pre+1,suf,sum[suf]-sum[pre]);
}
void calcL(int i){
    int pre=getmni(max(i-R,0),i-L);
    int suf=getmxi(i,min(pre+R,n));
    update(1,1,n,pre+1,suf,sum[suf]-sum[pre]);
}
void spread(int pt){
    tag[pt*2]=max(tag[pt*2],tag[pt]);
    tag[pt*2+1]=max(tag[pt*2+1],tag[pt]);
}
void solve(int pt,int l,int r){
    if (l==r){
        write(tag[pt]);putchar(' ');return ;
    }spread(pt);
    int mid=(l+r)/2;
    solve(pt*2,l,mid);solve(pt*2+1,mid+1,r);
    return ;
}

int main(){
	freopen ("wwydatsv.in","r",stdin);
	freopen ("wwydatsv.out","w",stdout);
	scanf("%d%d%d",&n,&L,&R);lgn=1.0*log(n+1)/log(2);
	mx[0][0]=mn[0][0]=mxi[0][0]=mni[0][0]=0;
	for (int i=1;i<=n;i++){
	    a[i]=read();
	    sum[i]=sum[i-1]+a[i];
	    mx[0][i]=mn[0][i]=sum[i];
	    mxi[0][i]=mni[0][i]=i;
    }
    prework();
    memset(tag,0xcf,sizeof(tag));
    for (int i=1;i<=n;i++){
        if (i+L-1<=n)calcR(i);
        if (i-L+1>=1)calcL(i);
    }
    solve(1,1,n);
    return 0;
}