题目分类：教义问答手册

上面的分类是瞎搞的

实际上是：动态规划，分块。

题意：

参见http://www.lydsy.com/JudgeOnline/problem.php?id=3636

题解：

考虑朴素的动态规划f[i]表示进行到第i位的结果，转移是向前取l个还是不取。

考虑第二个部分分，可以发现可以使用线段树维护，在合并区间的时候需要枚举截点是一个l的哪个位置。

得到思路可以进行分块，对于每个询问考虑如果不跨越区块就随意，跨越区块就取开头的第一个分界进行枚举，需要预处理一大堆动态规划值。

一堆细节神烦。

程序：

#include<cstdio>
#include<cstring>
#include<utility>
#include<vector>
#include<algorithm>
using namespace std;
pair<pair<int,int>,int>qu[120000];
int lef[60][120000],rig[60][120000];
int n,m,q;
int x1,x2;
int s[120000];
int ans[120000];
int siz;
int dp[20000];
vector<int>divd[20000];
inline int bruteforce(int x,int y)
{
	memset(dp,0,sizeof(dp));
	for (int i=x;i<=y;i++)
	{
		int tp=i-x+1;
		if(tp>=m)dp[tp]=max(dp[tp-1],dp[tp-m]+s[i]-s[i-m]);
	}return dp[y-x+1];
}
inline int summ(int x,int y)
{
	return s[y]-s[x-1];
}
inline int rebuild(int x)
{
	memset(lef,0,sizeof(lef));
	memset(rig,0,sizeof(rig));
	for (int i=m;i>=0;i--)
	{
		for (int j=x-m+i+1;j>=x-siz+1;j--)
		{
			
			lef[i][j]=max(lef[i][j+1],lef[i][j+m]+summ(j,j+m-1));
		//	printf("lef:%d %d %d %d\n",x,i,j,lef[i][j]);
		}
	}
	for (int i=m;i>=0;i--)
	{
		int tp=x+i;
		for (int j=tp;j<=n;j++)
		{
			if(j-m>tp-1)
			rig[i][j]=max(rig[i][j-1],rig[i][j-m]+summ(j-m+1,j));
		//	printf("rig:%d %d %d %d\n",x,i,j,rig[i][j]);
		}
	}
}
inline int solve(int x,int y,int mid)
{
	int res=0;
	for (int i=m;i>=0;i--)
	{
		if(i+mid<=y)
		res=max(lef[i][x]+rig[i][y],res);
	}return res;
}
inline int getint()
{
	int mi=1,fl=0,res=0;
	char chx=getchar();
	while (1)
	{
		if(chx=='-')mi=-1;
		else if(chx<='9'&&chx>='0')
		{
			res*=10;
			res+=chx-'0';
			fl=1;
		}
		else
		{
			if(fl==1)break;
		}chx=getchar();
	}
	return mi*res;
}
int main()
{
	n=getint();m=getint();
	siz=10000;
	for (int i=1;i<=n;i++)
	{
		s[i]=getint();
		s[i]=s[i-1]+s[i];
	}
	q=getint();
	for (int i=1;i<=q;i++)
	{
		qu[i].first.first=getint();qu[i].first.second=getint();
		qu[i].second=i;
		if(qu[i].first.second-qu[i].first.first+1<=siz)
		{
			ans[qu[i].second]=bruteforce(qu[i].first.first,qu[i].first.second);
		//	printf("%d %d\n",i,qu[i].first.second-qu[i].first.first+1);
		}
		else divd[(qu[i].first.first-1)/siz+1].push_back(i);
	}
	for (int i=siz;i<n;i+=siz)
	{
		rebuild(i);//printf("%d\n",i);
		int pos=i/siz;
		int tp=divd[pos].size();
		for (int j=0;j<tp;j++)
		{
			ans[qu[divd[pos][j]].second]=solve(qu[divd[pos][j]].first.first,qu[divd[pos][j]].first.second,i);
		}
	}
	for (int i=1;i<=q;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}