同一道题 http://blog.csdn.net/zy691357966/article/details/44680121
区间查询最大值 用线段树 比单调队列慢
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x1313131
const int maxn=500000+5;
using namespace std;
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
long long N,A,B;
long long a[maxn],sum[maxn];
long long tree[maxn<<2];
void input()
{
scanf("%I64d%I64d%I64d",&N,&A,&B);
for(int i=1;i<=N;i++)
{
scanf("%I64d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
}
int build(long long l,long long r,int rt)
{
if(l==r) {tree[rt]=sum[l];return 0;}
long long m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
long long query(long long L,long long R,long long l,long long r,int rt)
{
long long temp=-5000000001,m;
if(L<=l&&r<=R) return tree[rt];
m=(l+r)>>1;
if(L<=m) temp=max(temp,query(L,R,l,m,rt<<1));
if(R>m) temp=max(temp,query(L,R,m+1,r,rt<<1|1));
return temp;
}
void solve()
{
long long ans=-5000000001;
build(1,N,1);
for(int i=1;i+A-1<=N;i++)
{
long long temp=0;
if(i+B-1<=N)
temp=query(i+A-1,i+B-1,1,N,1);
else temp=query(i+A-1,N,1,N,1);
if(ans<temp-sum[i-1]) ans=temp-sum[i-1];
}
printf("%I64d
",ans);
}
int main()
{
//init();
int T;
cin>>T;
while(T--)
{
input();
solve();
}
}