同一道题  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\n",ans);

}

int main()

{

	//init();

	int T;

	cin>>T;

	while(T--)

    {

        input();

        solve();

    }

}