[BZOJ3636]教义问答手册

本文主要是介绍[BZOJ3636]教义问答手册，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

教义问答手册

题解

挺简单的一道二分。

首先看到题目首先应该很容易想到dp，毕竟用dp求这个最大值应该是很简单的。
但是由于询问太多，我们不可能对每个询问都做一次dp，考虑整体二分。
对于二分时，我们处理掉所有当前的过 $m i d$ 的询问。
可以通过分别求出左边的dp值与右边的dp值来计算。
由于涉及到合并的问题，我们的状态 $dp_{i,j}$ 分别要记录它到了哪个点与它在 $m i d$ 处连续选的点的数量，表示选到第 $i$ 个点， $m i d$ 处连续选了 $j$ 个，时的最大值。
合并的时候只需要从 $0$ 到 $L$ 枚举两边的dp来合并即可。
dp转移也就是一个很常见方法， $dp_{i,j}=max(dp_{i-1,j},dp_{i-L,j}+\sum_{j=i-L+1}^{i}a_{j})$ 。
后面的求和可以用前缀和预处理出来。
注意由于要求前面与后面两段，要做两次dp。

总时间复杂度为 $O\left((n+q)Llog\, n\right)$ ，还是可以过的。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int mo=1e9+7;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
int n,L,q,a[MAXN],b[MAXN],c[MAXN],d[MAXN],pre[MAXN],suf[MAXN];
int f[MAXN][55],g[MAXN][55],sum[MAXN],ans[MAXN];
struct ming{int l,r;}s[MAXN];
void sakura(int l,int r,int al,int ar){int mid=l+r>>1;if(al>ar)return ;if(r-l+1<L){for(int i=al;i<=ar;i++)ans[b[i]]=0;return ;}if(l==r){for(int i=al;i<=ar;i++)ans[b[i]]=max(a[l],0);return ;}for(int i=0;i<=L;i++)f[mid][i]=sum[mid]-sum[mid-i];for(int i=mid-1;i>=l;i--)for(int j=0;j<=L;j++)if(i+L-1>mid-j)f[i][j]=f[i+1][j];else f[i][j]=max(f[i+1][j],f[i+L][j]+pre[i]);for(int i=mid;i>=max(mid-L+1,l);i--)for(int j=mid-i+2;j<=L;j++)f[i][j]=-INF;for(int i=0;i<=L;i++)g[mid+1][i]=sum[mid+i]-sum[mid];for(int i=mid+2;i<=r;i++)for(int j=0;j<=L;j++)if(i-L+1<=mid+j)g[i][j]=g[i-1][j];else g[i][j]=max(g[i-1][j],g[i-L][j]+suf[i]);for(int i=mid+1;i<=min(mid+L,r);i++)for(int j=i-mid+1;j<=L;j++)g[i][j]=-INF;for(int i=al;i<=ar;i++)if(s[b[i]].l<=mid&&mid<s[b[i]].r){int tmp=max(0,f[s[b[i]].l][0]+g[s[b[i]].r][0]);	for(int k=0;k<=L;k++)tmp=max(f[s[b[i]].l][k]+g[s[b[i]].r][L-k],tmp);ans[b[i]]=max(tmp,f[s[b[i]].l][L]+g[s[b[i]].r][L]);}int j=0,k=0;for(int i=al;i<=ar;i++){if(s[b[i]].r<=mid)c[++j]=b[i];if(s[b[i]].l>mid)d[++k]=b[i];}for(int i=al;i<al+j;i++)b[i]=c[i-al+1],c[i-al+1]=0;for(int i=ar;i>ar-k;i--)b[i]=d[ar-i+1],d[ar-i+1]=0;for(int i=l;i<=r;i++)for(int j=0;j<=L;j++)f[i][j]=g[i][j]=0;sakura(l,mid,al,al+j-1);sakura(mid+1,r,ar-k+1,ar);
}
signed main(){read(n);read(L);for(int i=1;i<=n;i++)read(a[i]),sum[i]=sum[i-1]+a[i];for(int i=1;i<=n;i++)pre[i]=sum[i+L-1]-sum[i-1],suf[i]=sum[i]-sum[i-L];read(q);for(int i=1;i<=q;i++)read(s[i].l),read(s[i].r),b[i]=i;sakura(1,n,1,q);for(int i=1;i<=q;i++)printf("%d\n",ans[i]);return 0;
}