首页 > 代码库 > SPOJ GSS5 Can you answer these queries V

SPOJ GSS5 Can you answer these queries V

 

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:26 3 -2 1 -4 5 221 1 2 31 3 2 51 111 1 1 1Output:231

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.

 

又是查询最大连续字段和,但是限制了左右端点所在的区间……

线段树的部分不需要改动,计算答案的时候改一下即可。

如果区间有重复部分,就把区间分成三段,左段里找左端点,右段里找右端点,然后并上中段。有一串麻烦的判断,具体看代码。

如果区间没有重复部分,就左段里找左端点,右段里找右端点,然后强制加上两区间中间的序列和。

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #define lc rt<<1  8 #define rc rt<<1|1  9 using namespace std; 10 const int mxn=100010; 11 int read(){ 12     int x=0,f=1;char ch=getchar(); 13     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();} 14     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();} 15     return x*f; 16 } 17 int n,m; 18 int data[mxn]; 19 struct node{ 20     int mx; 21     int ml,mr; 22     int smm; 23 }t[mxn<<2],tmp0; 24 void Build(int l,int r,int rt){ 25     if(l==r){t[rt].mx=t[rt].ml=t[rt].mr=data[l];t[rt].smm=data[l];return;} 26     int mid=(l+r)>>1; 27     Build(l,mid,lc); 28     Build(mid+1,r,rc); 29     t[rt].smm=t[lc].smm+t[rc].smm; 30     t[rt].mx=max(t[lc].mx,t[rc].mx); 31     t[rt].mx=max(t[lc].mr+t[rc].ml,t[rt].mx); 32     t[rt].ml=max(t[lc].ml,t[lc].smm+t[rc].ml); 33     t[rt].mr=max(t[rc].mr,t[rc].smm+t[lc].mr); 34     return; 35 } 36 node query(int L,int R,int l,int r,int rt){ 37 //    printf("%d %d %d %d %d\n",L,R,l,r,rt); 38     if(R<L){ 39         return (node){0,0,0,0}; 40     } 41     if(L<=l && r<=R){return t[rt];} 42     int mid=(l+r)>>1; 43     node res1; 44     if(L<=mid)res1=query(L,R,l,mid,lc); 45         else res1=tmp0; 46     node res2; 47     if(R>mid)res2=query(L,R,mid+1,r,rc); 48         else res2=tmp0; 49     node res={0}; 50     res.smm=res1.smm+res2.smm; 51     res.mx=max(res1.mx,res2.mx); 52     res.mx=max(res.mx,res1.mr+res2.ml); 53     res.ml=max(res1.ml,res1.smm+res2.ml); 54     res.mr=max(res2.mr,res2.smm+res1.mr); 55     return res; 56 } 57 int qsum(int L,int R,int l,int r,int rt){ 58     if(L<=l && r<=R)return t[rt].smm; 59     int mid=(l+r)>>1; 60     int res=0; 61     if(L<=mid)res+=qsum(L,R,l,mid,lc); 62     if(R>mid)res+=qsum(L,R,mid+1,r,rc); 63     return res; 64 } 65 int main(){ 66     int T; 67     T=read(); 68     while(T--){ 69         n=read(); 70         int i,j,x0,y0,x2,y2; 71         for(i=1;i<=n;i++)data[i]=read(); 72         Build(1,n,1); 73         m=read(); 74         tmp0.ml=tmp0.mr=tmp0.mx=-1e9;tmp0.smm=0; 75         for(i=1;i<=m;i++){ 76             x0=read();y0=read();x2=read();y2=read(); 77             int tmp=0; 78             int ans=-1e9; 79             if(y0>=x2){ 80             //区间重叠 81                 node res=query(x2,y0,1,n,1); 82                 node res1=query(x0,x2-1,1,n,1); 83                 node res2=query(y0+1,y2,1,n,1); 84                 ans=max(ans,res1.mr+res.smm+res2.ml); 85                 ans=max(ans,res1.mr+res.ml); 86                 ans=max(ans,res.mr+res2.ml); 87                 ans=max(ans,res.mx); 88             } 89             else{ 90             //区间未重叠 91                 if(y0+1<x2)tmp=qsum(y0+1,x2-1,1,n,1); 92                 node res1=query(x0,y0,1,n,1); 93                 node res2=query(x2,y2,1,n,1); 94                 ans=max(ans,tmp+res1.mr+res2.ml); 95             } 96             //printf("%d\n",query(x2,y2,1,n,1).mx); 97             printf("%d\n",ans); 98         } 99     }100     return 0;101 }

 

SPOJ GSS5 Can you answer these queries V