首页 > 代码库 > SPOJ GSS1 Can you answer these queries I

SPOJ GSS1 Can you answer these queries I

2024-08-24 04:43:10   225人阅读

 

Time Limit: 115MS Memory Limit: 1572864KB 64bit IO Format: %lld & %llu

Description

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: 
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }. 
Given M queries, your program must output the results of these queries.

Input

  • The first line of the input file contains the integer N.
  • In the second line, N numbers follow.
  • The third line contains the integer M.
  • M lines follow, where line i contains 2 numbers xi and yi.

Output

    Your program should output the results of the M queries, one query per line.

Example

Input:3 -1 2 311 2Output:2

Hint

Added by:Nguyen Dinh Tu
Date:2006-11-01
Time limit:0.115s-0.230s
Source limit:5000B
Memory limit:1536MB
Cluster:Cube (Intel G860)
Languages:All except: ERL JS NODEJS PERL 6 VB.net

 

询问区间内和最大的连续子序列。没有修改操作。

线段树维护即可。

 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(L<=l && r<=R){return t[rt];}39     int mid=(l+r)>>1;40     node res1;41     if(L<=mid)res1=query(L,R,l,mid,lc);42         else res1=tmp0;43     node res2;44     if(R>mid)res2=query(L,R,mid+1,r,rc);45         else res2=tmp0;46     node res={0};47     res.smm=res1.smm+res2.smm;48     res.mx=max(res1.mx,res2.mx);49     res.mx=max(res.mx,res1.mr+res2.ml);50     res.ml=max(res1.ml,res1.smm+res2.ml);51     res.mr=max(res2.mr,res2.smm+res1.mr);52     return res;53 }54 int main(){55     n=read();56     int i,j,x,y;57     for(i=1;i<=n;i++)data[i]=read();58     Build(1,n,1);59     m=read();60     tmp0.ml=tmp0.mr=tmp0.mx=-1e9;tmp0.smm=0;61     for(i=1;i<=m;i++){62         x=read();y=read();63         printf("%d\n",query(x,y,1,n,1).mx);64     }65     return 0;66 }

 

SPOJ GSS1 Can you answer these queries I


联系
我们