uvaLive3938:

题意：给你n个数，然后给你一个区间，让你查询这个区间内最大和连续子区间。

题解：哎。智商是硬伤啊，虽然线段树也做过不少题目，但是遇到这样的题目还是不会处理啊，看了别人的代码才明白了怎么做。用那个线段树维护区间最大前缀，最大后缀，以及真正的最大区间。要注意父节点这三个变量是怎么由子节点推导出来的。还是贴代码吧。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 const int N=500009;  7 int ll[N*3],rr[N*3];  8 struct  Node{  9    int pre,suf; 10    int vx,vy; 11 }num[N*3]; 12 long long sum[N]; 13 void pushup(int rt,int l,int r){ 14     if(sum[num[rt<<1].pre]-sum[l-1]>=sum[num[rt<<1|1].pre]-sum[l-1]) 15         num[rt].pre=num[rt<<1].pre; 16     else 17         num[rt].pre=num[rt<<1|1].pre; 18     if(sum[r]-sum[num[rt<<1].suf-1]>=sum[r]-sum[num[rt<<1|1].suf-1]) 19         num[rt].suf=num[rt<<1].suf; 20     else 21         num[rt].suf=num[rt<<1|1].suf; 22     long long v1=sum[num[rt<<1].vy]-sum[num[rt<<1].vx-1]; 23     long long v2=sum[num[rt<<1|1].vy]-sum[num[rt<<1|1].vx-1]; 24     long long v0=sum[num[rt<<1|1].pre]-sum[num[rt<<1].suf-1]; 25     if(v1>=v2){ 26         num[rt].vx=num[rt<<1].vx; 27         num[rt].vy=num[rt<<1].vy; 28     } 29     else{ 30         num[rt].vx=num[rt<<1|1].vx; 31         num[rt].vy=num[rt<<1|1].vy; 32     } 33     if(v0==sum[num[rt].vy]-sum[num[rt].vx-1]){ 34         if(num[rt<<1].suf
          
           sum[num[rt].vy]-sum[num[rt].vx-1]){ 40          num[rt].vx=num[rt<<1].suf; 41         num[rt].vy=num[rt<<1|1].pre; 42     } 43 } 44 void build(int rt,int l,int r){ 45      ll[rt]=l; 46      rr[rt]=r; 47      if(l==r){ 48         num[rt].pre=num[rt].suf=num[rt].vx=num[rt].vy=l; 49         return; 50      } 51     int mid=(l+r)/2; 52     build(rt<<1,l,mid); 53     build(rt<<1|1,mid+1,r); 54     pushup(rt,l,r); 55 } 56 Node query(int rt,int s,int t){ 57     if(ll[rt]==s&&rr[rt]==t) 58         return num[rt]; 59      int mid=(ll[rt]+rr[rt])/2; 60     if(mid>=t)return query(rt<<1,s,t); 61     else if(mid
           
            =sum[temp2.pre]-sum[s-1]) 67 temp.pre=temp1.pre; 68 else 69 temp.pre=temp2.pre; 70 if(sum[t]-sum[temp1.suf-1]>=sum[t]-sum[temp2.suf-1]) 71 temp.suf=temp1.suf; 72 else 73 temp.suf=temp2.suf; 74 long long v1=sum[temp1.vy]-sum[temp1.vx-1]; 75 long long v2=sum[temp2.vy]-sum[temp2.vx-1]; 76 long long v0=sum[temp2.pre]-sum[temp1.suf-1]; 77 if(v1>=v2){ 78 temp.vx=temp1.vx; 79 temp.vy=temp1.vy; 80 } 81 else{ 82 temp.vx=temp2.vx; 83 temp.vy=temp2.vy; 84 } 85 if(v0==sum[temp.vy]-sum[temp.vx-1]){ 86 if(temp1.suf
            
             sum[temp.vy]-sum[temp.vx-1]){ 92 temp.vx=temp1.suf; 93 temp.vy=temp2.pre; 94 } 95 return temp; 96 } 97 } 98 int main(){ 99 int cas=0,n,m,l,r;100 long long tp;101 while(~scanf("%d%d",&n,&m)){102 memset(sum,0,sizeof(sum));103 for(int i=1;i<=n;i++){104 scanf("%lld",&tp);105 sum[i]=sum[i-1]+tp;106 }107 build(1,1,n);108 printf("Case %d:\n",++cas);109 for(int i=1;i<=m;i++){110 scanf("%d%d",&l,&r);111 Node ans=query(1,l,r);112 printf("%d %d\n",ans.vx,ans.vy);113 }114 }115 116 }