| Time Limit: 132MS | Memory Limit: 1572864KB | 64bit IO Format: %lld & %llu |
Description
You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| <= 10000 , 1 <= N <= 10000 ). A query is defined as follows: Query(x1,y1,x2,y2) = Max { A[i]+A[i+1]+...+A[j] ; x1 <= i <= y1 , x2 <= j <= y2 and x1 <= x2 , y1 <= y2 }. Given M queries (1 <= M <= 10000), your program must output the results of these queries.
Input
The first line of the input consist of the number of tests cases <= 5. Each case consist of the integer N and the sequence A. Then the integer M. M lines follow, contains 4 numbers x1, y1, x2 y2.
Output
Your program should output the results of the M queries for each test case, one query per line.
Example
Input:
2
6 3 -2 1 -4 5 2
2
1 1 2 3
1 3 2 5
1 1
1
1 1 1 1 Output:
2
3
1
Hint
| Added by: | Frank Rafael Arteaga |
| Date: | 2008-08-06 |
| Time limit: | 0.132s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: C99 strict ERL JS NODEJS PERL 6 VB.net |
| Resource: | K.-Y. Chen and K.-M. Chao, On the Range Maximum-Sum Segment Query Problem, 2007. |
又是查询最大连续字段和，但是限制了左右端点所在的区间……
线段树的部分不需要改动，计算答案的时候改一下即可。
如果区间有重复部分，就把区间分成三段，左段里找左端点，右段里找右端点，然后并上中段。有一串麻烦的判断，具体看代码。
如果区间没有重复部分，就左段里找左端点，右段里找右端点，然后强制加上两区间中间的序列和。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define lc rt<<1
#define rc rt<<1|1
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m;
int data[mxn];
struct node{
int mx;
int ml,mr;
int smm;
}t[mxn<<],tmp0;
void Build(int l,int r,int rt){
if(l==r){t[rt].mx=t[rt].ml=t[rt].mr=data[l];t[rt].smm=data[l];return;}
int mid=(l+r)>>;
Build(l,mid,lc);
Build(mid+,r,rc);
t[rt].smm=t[lc].smm+t[rc].smm;
t[rt].mx=max(t[lc].mx,t[rc].mx);
t[rt].mx=max(t[lc].mr+t[rc].ml,t[rt].mx);
t[rt].ml=max(t[lc].ml,t[lc].smm+t[rc].ml);
t[rt].mr=max(t[rc].mr,t[rc].smm+t[lc].mr);
return;
}
node query(int L,int R,int l,int r,int rt){
// printf("%d %d %d %d %d\n",L,R,l,r,rt);
if(R<L){
return (node){,,,};
}
if(L<=l && r<=R){return t[rt];}
int mid=(l+r)>>;
node res1;
if(L<=mid)res1=query(L,R,l,mid,lc);
else res1=tmp0;
node res2;
if(R>mid)res2=query(L,R,mid+,r,rc);
else res2=tmp0;
node res={};
res.smm=res1.smm+res2.smm;
res.mx=max(res1.mx,res2.mx);
res.mx=max(res.mx,res1.mr+res2.ml);
res.ml=max(res1.ml,res1.smm+res2.ml);
res.mr=max(res2.mr,res2.smm+res1.mr);
return res;
}
int qsum(int L,int R,int l,int r,int rt){
if(L<=l && r<=R)return t[rt].smm;
int mid=(l+r)>>;
int res=;
if(L<=mid)res+=qsum(L,R,l,mid,lc);
if(R>mid)res+=qsum(L,R,mid+,r,rc);
return res;
}
int main(){
int T;
T=read();
while(T--){
n=read();
int i,j,x0,y0,x2,y2;
for(i=;i<=n;i++)data[i]=read();
Build(,n,);
m=read();
tmp0.ml=tmp0.mr=tmp0.mx=-1e9;tmp0.smm=;
for(i=;i<=m;i++){
x0=read();y0=read();x2=read();y2=read();
int tmp=;
int ans=-1e9;
if(y0>=x2){
//区间重叠
node res=query(x2,y0,,n,);
node res1=query(x0,x2-,,n,);
node res2=query(y0+,y2,,n,);
ans=max(ans,res1.mr+res.smm+res2.ml);
ans=max(ans,res1.mr+res.ml);
ans=max(ans,res.mr+res2.ml);
ans=max(ans,res.mx);
}
else{
//区间未重叠
if(y0+<x2)tmp=qsum(y0+,x2-,,n,);
node res1=query(x0,y0,,n,);
node res2=query(x2,y2,,n,);
ans=max(ans,tmp+res1.mr+res2.ml);
}
//printf("%d\n",query(x2,y2,1,n,1).mx);
printf("%d\n",ans);
}
}
return ;
}