https://www.luogu.org/problemnew/show/P1714
题目中文的不说了；
做法：首先预处理前缀和，然后答案就是 sum[i]-sum[j] j的范围就是i-m到i-1或者i（这个题目叙述问题，没有说不能不吃）；
然后对于每一个i来说，sum[i]的大小是固定的，于是就是区间i-m到i-1的最小值了，然后求每一个i对应的最大值的最大值；
这样就可以用用单调队列维护，或者，线段树等。
单调队列
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=5e5+10; int n,m,a[N],sum[N]; int que[N],head,tail,id[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m;a[0]=0; for(int i=1;i<=n;i++) cin>>a[i]; sum[0]=0; for(int i=1;i<=n;i++) sum[i]+=sum[i-1]+a[i]; int ans=0; head=1,tail=0; for(int i=1;i<=n;i++) { while(head<=tail&&que[tail]>=sum[i-1]) tail--; que[++tail]=sum[i-1],id[tail]=i-1; while(id[head]<i-m) head++; ans=max(sum[i]-que[head],ans); } printf("%d\n",ans); return 0; }线段树时间复杂度nlogn
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=5e5+10; int n,m,a[N],sum[N]; int que[N],head,tail,id[N]; int rt[N<<2]; void build(int o,int l,int r) { if(l==r){ rt[o]=sum[l]; return; } int mid=l+r>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); rt[o]=min(rt[o<<1],rt[o<<1|1]); } int query(int o,int l,int r,int ql,int qr) { if(ql==l&&qr==r){ return rt[o]; } int mid=l+r>>1; int ans=0; if(qr<=mid) ans=query(o<<1,l,mid,ql,qr); else if(ql>mid) ans=query(o<<1|1,mid+1,r,ql,qr); else{ ans=min(query(o<<1,l,mid,ql,mid),query(o<<1|1,mid+1,r,mid+1,qr)); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m;a[0]=0; for(int i=1;i<=n;i++) cin>>a[i]; sum[0]=0; for(int i=1;i<=n;i++) sum[i]+=sum[i-1]+a[i]; build(1,1,n); int ans=sum[1]; for(int i=2;i<=n;i++){ int t=query(1,1,n,max(1,i-m),i-1); ans=max(ans,sum[i]-t); } cout<<ans<<endl; return 0; }
