好题。

1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5 int CASE=1;  6 const int maxn=500000+5;  7 typedef long long LL;  8 typedef  pair
        
          Interval;  9 int qL,qR; 10 LL s[maxn]; 11 Interval max_sub[maxn<<1]; 12 LL max_prefix[maxn<<1]; 13 LL max_suffix[maxn<<1]; 14 LL sum(int l,int r) 15 { 16     return s[r]-s[l-1]; 17 } 18 LL sum(Interval x) 19 { 20     return s[x.second]-s[x.first-1]; 21 } 22 Interval better(Interval a,Interval b) 23 { 24     if(sum(a)==sum(b)) return a
         
          sum(b)?a:b; 26 } 27 void build(int l,int r,int rt) 28 { 29    if(l==r) 30    { 31      max_prefix[rt]=max_suffix[rt]=l; 32      max_sub[rt]=make_pair(l,l); 33      return ; 34    } 35    else 36    { 37     int m=l+(r-l)/2; 38     build(l,m,rt<<1); 39     build(m+1,r,rt<<1|1); 40  41     LL v1=sum(l,max_prefix[rt<<1]); 42     LL v2=sum(l,max_prefix[rt<<1|1]); 43     if(v1==v2) max_prefix[rt]=min(max_prefix[rt<<1],max_prefix[rt<<1|1]); 44     else  max_prefix[rt]=v1>v2?max_prefix[rt<<1]:max_prefix[rt<<1|1]; 45  46     v1=sum(max_suffix[rt<<1],r); 47     v2=sum(max_suffix[rt<<1|1],r); 48     if(v1==v2) max_suffix[rt]=min(max_suffix[rt<<1],max_suffix[rt<<1|1]); 49     else  max_suffix[rt]=v1>v2?max_suffix[rt<<1]:max_suffix[rt<<1|1]; 50  51     max_sub[rt]=better(max_sub[rt<<1],max_sub[rt<<1|1]); 52     max_sub[rt]=better(max_sub[rt],make_pair(max_suffix[rt<<1],max_prefix[rt<<1|1])); 53    } 54 } 55 Interval prefix_query(int l,int r,int rt) 56 { 57     if(max_prefix[rt]<=qR) return make_pair(l,max_prefix[rt]); 58     int m=l+(r-l)/2; 59     if(qR<=m) return prefix_query(l,m,rt<<1); 60     Interval i=prefix_query(m+1,r,rt<<1|1); 61     i.first=l; 62     return better(i,make_pair(l,max_prefix[rt<<1])); 63 } 64 Interval suffix_query(int l,int r,int rt) 65 { 66     if(max_suffix[rt]>=qL) return make_pair(max_suffix[rt],r); 67     int m=l+(r-l)/2; 68     if(qL>m) return suffix_query(m+1,r,rt<<1|1); 69     Interval i=suffix_query(l,m,rt<<1); 70     i.second=r; 71     return better(i,make_pair(max_suffix[rt<<1|1],r)); 72 } 73 Interval query(int l,int r,int rt) 74 { 75     if(qL<=l&&r<=qR) 76       return max_sub[rt]; 77     int m=l+(r-l)/2; 78     if(qR<=m) return query(l,m,rt<<1); 79     if(qL>m) return query(m+1,r,rt<<1|1); 80     Interval i1=suffix_query(l,m,rt<<1); 81     Interval i2=prefix_query(m+1,r,rt<<1|1); 82     Interval i3=better(query(l,m,rt<<1),query(m+1,r,rt<<1|1)); 83     return better(i3,make_pair(i1.first,i2.second)); 84 } 85 int main() 86 { 87     int n,m; 88     while(scanf("%d%d",&n,&m)!=EOF) 89     { 90         int a; 91         s[0]=0; 92        for(int i=1;i<=n;i++) 93         { 94             scanf("%d",&a); 95             s[i]=s[i-1]+a; 96         } 97         build(1,n,1); 98        printf("Case %d:\n",CASE++); 99        while(m--)100        {101            int a,b;102            scanf("%d%d",&a,&b);103            qL=a,qR=b;104            Interval ans=query(1,n,1);105 106            printf("%d %d\n",ans.first,ans.second);107        }108     }109     return 0;110 }