题意：
给出一个长度为n的整数序列D，你的任务是对m各询问做出回答。对于询问(a,b)，需要找到两个下标x和y，使得a<=x<=y<=b，并且Dx+Dx+1+...+Dy尽量大。如果有多组满足条件的x和y，x应该尽量小。如果还有多解，y应该尽量小。
题解：
蓝书上的线段树练习题，做起来感觉还是不简单地，比起来前面做过的那些题，这种区间合并，多重递归的要复杂的多！
建立一颗线段树，每个节点维护以下信息：
max_sub : 本节点维护的最大连续和的子区间[L,R]
max_prefix : 本节点的最大前缀和区间的右端坐标R
max_suffix ：本节点的最大后缀和区间的左端坐标L
举个栗子：对于一个查询[20,50] 区间的最大连续和，由于区间被分成了[20,32],[33,50]，结果只有以下三种情况:
1. 最大连续和在[20,32]中，即max_sub[20,32]
2. 最大连续和在[33,50]中，即max_sub[33,50]
3. 最大连续和x在[20,32]中，y在[33,50]中。也就是max_sum[20,50]=max_suffix[20,32]+max_prefix[33,50],并且更新x,y的坐标。
难点就在于还要在递归的去求max_prefix,max_suffix。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<cctype>
#define INF 0x3f3f3f3fusing namespace std;#define lson 2*i,l,m
#define rson 2*i+1,m+1,rconst int maxn=500000+100;
typedef pair<int,int>pii;
pii max_sub[maxn<<2];
int max_prefix[maxn<<2],max_suffix[maxn<<2];long long prefix_sum[maxn];
//后面有两种调用方式。
long long get_sum(int l,int r)
{return prefix_sum[r]-prefix_sum[l-1];
}long long get_sum(pii p)
{return get_sum(p.first,p.second);
}pii better(pii a,pii b)
{if(get_sum(a)!=get_sum(b))return get_sum(a)>get_sum(b)?a:b;return a<b? a:b;
}void pushup(int i,int l,int r)
{//计算最大和max_sub[i]=better(max_sub[2*i],max_sub[2*i+1]);//直接从左边或者右边max_sub[i]=better(max_sub[i],pii(max_suffix[2*i],max_prefix[2*i+1]));//左半边和右半边都有//计算前缀long long x=get_sum(l,max_prefix[2*i]);//前缀和来自前半边long long y=get_sum(l,max_prefix[2*i+1]);//前缀和的右端点在右半边if(x==y)max_prefix[i]= max_prefix[2*i];//两者相等，取前半边else max_prefix[i]=x>y?max_prefix[2*i]:max_prefix[2*i+1];//计算后缀x=get_sum(max_suffix[i*2],r);y=get_sum(max_suffix[2*i+1],r);if(x==y) max_suffix[i]=max_suffix[2*i];else max_suffix[i]=x>y?max_suffix[2*i]:max_suffix[2*i+1];}void build(int i,int l,int r)
{if(l==r){max_sub[i]=pii(l,r);max_prefix[i]=max_suffix[i]=l;return;}int m=(l+r)/2;build(lson);build(rson);pushup(i,l,r);
}pii query_prefix(int ql,int qr,int i,int l,int r)
{if(max_prefix[i]<=qr)return pii(l,max_prefix[i]);int m=(l+r)/2;if(qr<=m)return query_prefix(ql,qr,lson);//干脆地去找左半区间pii a=query_prefix(ql,qr,rson);//找右半区间的最大前缀，此时区间左边不是l了。a.first=l;return better(a,pii(l,max_prefix[2*i]));//
}pii query_suffix(int ql,int qr,int i,int l,int r)
{if(max_suffix[i]>=ql)return pii(max_suffix[i],r);int m=(l+r)/2;if(m<ql)return query_suffix(ql,qr,rson);pii a=query_suffix(ql,qr,lson);a.second=r;return better(a,pii(max_suffix[2*i+1],r));
}pii query(int ql,int qr,int i,int l,int r)
{if(ql<=l&&qr>=r)return max_sub[i];int m=(l+r)/2;if(qr<=m)return query(ql,qr,lson);if(ql>m)return query(ql,qr,rson);int L=query_suffix(ql,qr,lson).first;int R=query_prefix(ql,qr,rson).second;pii a=better(query(ql,qr,lson),query(ql,qr,rson));//单独来自左半边或者右半边return better(pii(L,R),a);
}int main()
{int n,m;int kase=1;while(cin>>n>>m&&n&&m){prefix_sum[0]=0;for(int i=1; i<=n; i++){int x;scanf("%d",&x);prefix_sum[i]=prefix_sum[i-1]+x;}build(1,1,n);printf("Case %d:\n",kase++);while(m--){int x,y;scanf("%d%d",&x,&y);pii a=query(x,y,1,1,n);printf("%d %d\n",a.first,a.second);}}
}