I.九峰与分割序列
题意：
给出一个序列，将其分割成若干个子区间。
子区间的贡献为：若前一个子区间的长度大于k且该区间长度小于等于k，则贡献为区间和的两倍，否则贡献为区间和。
求一种分割方法，使得所有子区间贡献之和最大，输出最大贡献。
题解：
考虑DP。
定义(f(i,0))表示最后一段区间大于k的最优解。
定义(f(i,0))表示最后一段区间小于等于k的最优解。
可以写出以下转移方程：
(f(i,0)=max(f(i,0),max_{j=1}^{i-k-1}f(j,0)+sum_i-sum_j))
(f(i,0)=max(f(i,0),max_{j=1}^{i-k-1}f(j,1)+sum_i-sum_j))
(f(i,1)=max(f(i,1),max_{j=i-k}^{i-1}f(j,0)+sum_i*2-sum_j*2))
(f(i,1)=max(f(i,1),max_{j=i-k}^{i-1}f(j,1)+sum_i-sum_j))
这个转移方程看起来很难快速维护。
有一个巧妙的思路，就是把和(j)有关的项合并，这样就可以用线段树维护了。
开三棵线段树。
第一棵维护(f(i,0)-sum_i)。
第二棵维护(f(i,1)-sum_i)。
第三棵维护(f(i,0)-sum_i*2)。
这样在转移的过程中，从对应的线段树里查询，最后再把每个状态更新到对应的线段树里就行了。
// Problem: 九峰与分割序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9984/I
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int n,k,a[maxn];
struct node {
int i,l,r;
long long lazy,sum;
}segTree[maxn<<2][3];
void build (int i,int l,int r,int x) {
segTree[i][x].l=l;
segTree[i][x].r=r;
if (l==r) {
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid,x);
build(i<<1|1,mid+1,r,x);
}
void spread (int i,int x) {
if (segTree[i][x].lazy) {
segTree[i<<1][x].sum+=segTree[i][x].lazy;
segTree[i<<1][x].lazy+=segTree[i][x].lazy;
segTree[i<<1|1][x].sum+=segTree[i][x].lazy;
segTree[i<<1|1][x].lazy+=segTree[i][x].lazy;
segTree[i][x].lazy=0;
}
}
void up (int i,int l,int r,long long v,int x) {
if (segTree[i][x].l>=l&&segTree[i][x].r<=r) {
segTree[i][x].sum+=v;
segTree[i][x].lazy+=v;
return;
}
spread(i,x);
int mid=(segTree[i][x].l+segTree[i][x].r)>>1;
if (l<=mid) up(i<<1,l,r,v,x);
if (r>mid) up(i<<1|1,l,r,v,x);
segTree[i][x].sum=max(segTree[i<<1][x].sum,segTree[i<<1|1][x].sum);
}
long long query (int i,int l,int r,int x) {
if (l>r) return 0;
if (segTree[i][x].l>=l&&segTree[i][x].r<=r) {
return segTree[i][x].sum;
}
spread(i,x);
int mid=(segTree[i][x].l+segTree[i][x].r)>>1;
long long ans=-1e18;
if (l<=mid) ans=max(ans,query(i<<1,l,r,x));
if (r>mid) ans=max(ans,query(i<<1|1,l,r,x));
return ans;
}
long long sum[maxn];
long long f[maxn][2];
int main () {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d",a+i),sum[i]=sum[i-1]+a[i],f[i][0]=f[i][1]=-1e18;
//考虑DP
//f(i,0)表示最后一段区间大于k的最优解
//f(i,1)表示最后一段区间小于等于k的最优解
//f(i,0)=max(f(i,0),[j=k~i-k-1]f(j,0)+sum(i)-sum(j)
//f(i,0)=max(f(i,0),[j=1~i-k-1]f(j,1)+sum(i)-sum(j)
//f(i,1)=max(f(i,1),[j=i-k~i-1]f(j,0)+sum(i)*2-sum(j)*2
//f(i,1)=max(f(i,1),[j=i-k~i-1]f(j,1)+sum(i)-sum(j)
//把和j有关的项合并，就可以用线段树维护了，比赛的时候怎么就没想到呢
//开3颗线段树
//第一棵维护f(i,0)-sum(i)
//第二棵维护f(i,1)-sum(j)
//第三颗维护f(i,0)-sum(j)*2
build(1,1,n,0);
build(1,1,n,1);
build(1,1,n,2);
for (int i=1;i<=n;i++) {
if (i<=k) {
f[i][1]=sum[i];
up(1,i,i,f[i][1]-sum[i],1);
up(1,i,i,f[i][0]-sum[i],0);
up(1,i,i,f[i][0]-sum[i]*2,2);
}
else {
f[i][0]=max(f[i][0],query(1,1,i-k-1,0)+sum[i]);
f[i][0]=max(f[i][0],query(1,1,i-k-1,1)+sum[i]);
f[i][1]=max(f[i][1],query(1,i-k,i-1,2)+sum[i]*2);
f[i][1]=max(f[i][1],query(1,i-k,i-1,1)+sum[i]);
up(1,i,i,f[i][0]-sum[i],0);
up(1,i,i,f[i][1]-sum[i],1);
up(1,i,i,f[i][0]-sum[i]*2,2);
}
}
printf("%lld
",max(f[n][0],f[n][1]));
}