题解 P1714 【切蛋糕】
我一开始以为这题就是普通的线段树求区间和，于是愉快地打起了板子。
然后发现事情好像不是这样的。。。。。。（血崩）k是1~m的，而且蛋糕还有负数幸运值（卧槽毒奶做的蛋糕？）
我打开了题解冥思苦想，线段树实现的话需要枚举左右端点，复杂度是O(N^2)，明显过不了，我们需要O(N)的复杂度。
如果用前缀和进行预处理，然后我们只需要枚举右端点，然后在范围内用线段树求出左端点就ok啦，虽然不是O（N）的复杂度，但是也刚好是符合题目的蛋糕范围的。
贴上我最喜欢的线段树代码（雾）（我怎么又交了一个线段树题解？）
#include <bits/stdc++.h>
using namespace std;
int n;
long long minn[4000000];
int a[1000000];
long long c[1000000];
void build(int l,int r,int id)
{
if(l==r)
{
minn[id]=c[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,id*2);
build(mid+1,r,id*2+1);
minn[id]=min(minn[id*2],minn[id*2+1]);
}
long long cck(int l,int r,int z,int y,int id)
{
if(l==z&&r==y)
{
return minn[id];
}
int mid=(l+r)/2;
if(mid>=y)return cck(l,mid,z,y,id*2);
else if(mid<z)return cck(mid+1,r,z,y,id*2+1);
else return min(cck(l,mid,z,mid,id*2),cck(mid+1,r,mid+1,y,id*2+1));
}
long long maxn;
int k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
c[i]=c[i-1]+a[i];
}
build(1,n,1);
for(int i=1;i<=n;i++)
{
maxn=max(c[i]-cck(1,n,max(i-k,1),i,1),maxn);
}
printf("%d\n",maxn);
return 0;
}