最大连续和

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 61(13 users)

Total Accepted: 15(9 users)

Rating:

Special Judge: No

Description

给出一个长度为n的整数序列D，你的任务是对m个询问做出回答。对于询问(a,b)，需要找到

两个下标x和y,使得a<=x<=y<=b，并且Dx+Dx+1+....+Dy尽量大。如果有多组满足条件的x和y，x

应尽量小。如果还有多解y也应尽量小。

Input

第一行是一个整数T，代表测试数据组数。

对于每组测试数据，第一行为一个整数(1<=n,m<=500000)，即整数序列的查询的个数。

第二行包含n个整数，依次为D1,D2,...Dn的值。这些整数绝对值不超过10^9。以下m行

每行为一个查询，包含两个整数a和b。

Output

对于每组数据，对于每个查询输出一行包含两个整数x和y。

Sample Input

1 8 3 -2 3 4 -6 6 10 -7 100 1 8 3 5 6 8

Sample Output

2 8 5 5 6 8

Author

陈禹@HRBUST

 一开始写出了这样的代码；

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long  LONG;LONG p[500000];struct node{    LONG sum;    int left,right;};node check(int i1,int i2){    node no,max;    no.sum=0;    no.left=i1;    no.right=i1-1;    //max.sum=-9223372036854775808;    max.sum=-5000000;    max.left=i1;    max.right=i1;    int i;    for(i=i1;i<=i2;i++)    {        no.sum+=p[i];        no.right++;    //    cout<
         
          <
          
           max.sum) { max=no; // cout<
           
            <
           
          
         
        
       
      
     

果断超时

后来想到线段树：

写出了代码，中间出了很多错误，基本都是脑残错误

原理：

每次需要比较左右子树

最大值的比较：

只需要比较三段，（1）max_left,(2)max_right(3)max_left_suffix+max_right_prefix

以最左边第一个元素为起点的最大值,为什么要更新他，为了使其父亲线段获得最大值

（1）比较 max_left_prefix与left_all+max_right_prefix

以最右边最后一个元素开始往左的最大值

（1）比较max_right_suffix与right_all+max_left_suffix

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int SIZE=500005;typedef long  LL;struct node{    LL sum,all;    int pre_r,suf_l;    int max_l,max_r;    LL prefixSum,suffixSum;} p[SIZE<<2];LL a[SIZE];void pushup(int L,int R,int rt){    int ll=rt<<1;    int rr=rt<<1|1;    p[rt].all=p[ll].all+p[rr].all;    p[rt].prefixSum=p[ll].prefixSum;    p[rt].pre_r=p[ll].pre_r;    p[rt].suffixSum=p[rr].all+p[ll].suffixSum;    p[rt].suf_l=p[ll].suf_l;    p[rt].sum=p[ll].sum;    p[rt].max_l=p[ll].max_l;    p[rt].max_r=p[ll].max_r;    if(p[rt].sum
         
          p[ll].suf_l))    {        p[rt].sum=p[ll].suffixSum+p[rr].prefixSum;        p[rt].max_l=p[ll].suf_l;        p[rt].max_r=p[rr].pre_r;    }    if(p[rt].prefixSum
          
           >1; int ll=rt<<1; int rr=rt<<1|1; build(L,m,ll); build(m+1,R,rr); pushup(L,R,rt);}node query(int L,int R,int l,int r,int rt){ if(L==l&&R==r) { return p[rt]; } /* if(L==R) 这一段时不可取的，这回大大投稿时间复杂度 { return p[rt]; }*/ int m=(L+R)>>1; int ll=rt<<1; int rr=rt<<1|1; if(m
           
            =r) { return query(L,m,l,r,ll); } node x=query(L,m,l,m,ll); node y=query(m+1,R,m+1,r,rr); node z; z.all=x.all+y.all; z.sum=x.sum; z.max_l=x.max_l; z.max_r=x.max_r; z.prefixSum=x.prefixSum; z.pre_r=x.pre_r; z.suffixSum=x.suffixSum+y.all; z.suf_l=x.suf_l; if(z.sum
            
             x.suf_l)) { z.sum=x.suffixSum+y.prefixSum; z.max_l=x.suf_l; z.max_r=y.pre_r; } if(z.prefixSum