90分求助

记录，第 9 个点 WA 了，写的是线段树优化 DP。

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,k,a[200050],f[200050],ans,sum[2000050];
struct node{
    int l,r,dat;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define dat(x) tree[x].dat
}tree[200050*4];
void build(int l,int r,int p){
    l(p)=l;
    r(p)=r;
    if(l==r){
        dat(p)=f[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    dat(p)=max(dat(p<<1),dat(p<<1|1));
}
void change(int p,int x,int d){
    if(l(p)==r(p)){
        dat(p)=d;
        return;
    }
    int mid=(l(p)+r(p))>>1;
    if(x<=mid) change(p<<1,x,d);
    else change(p<<1|1,x,d);
    dat(p)=max(dat(p<<1),dat(p<<1|1));
}
int ask(int l,int r,int p){
    if(l<=l(p) && r>=r(p)){
        return dat(p);
    }
    int mid=(l(p)+r(p))>>1,num=-0x7fffffff;
    if(l<=mid) num=max(num,ask(l,r,p<<1));
    if(r>mid) num=max(num,ask(l,r,p<<1|1));
    return num;
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    n++;
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    build(0,n,1);
    change(1,1,f[1]-sum[1]);
    for(int i=2;i<=n;i++){
        f[i]=sum[i-1]+ask(max(i-k,1ll)-1,i-1,1);
        change(1,i,f[i]-sum[i]);
    }
    cout<<f[n];
    return 0;
}